📖 문제
🔧 풀이법
기본 시뮬레이션 문제이다.
bfs를 돌릴 때 경로를 저장하는 것이 포인트!
1. towerList와 tCnt를 사용해서 공격할 수 있는 포탑을 관리함
2. bfs를 사용해서 laser 공격을 구현함. Point[][] route 배열을 생성해서 경로를 저장할 수 있도록 하였다!
✏️ 소감
bomb() 함수에서.. 변수 오타를 내서 디버깅하는데 한참 걸렸다..... 땋..
🖥️ 코드
package codetree;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Codetree_포탑부수기 {
static class Point {
int x, y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + "]";
}
}
static class Tower implements Comparable<Tower> {
int x, y;
int power;
int time;
public Tower(int x, int y, int power, int time) {
super();
this.x = x;
this.y = y;
this.power = power;
this.time = time;
}
@Override
public int compareTo(Tower o) {
if(this.power != o.power) return this.power - o.power;
if(this.time != o.time) return o.time - this.time;
if((this.x+this.y) != (o.x + o.y)) return (o.x + o.y) - (this.x + this.y);
return o.y - this.y;
}
}
static int N, M, K;
static Tower[][] map;
static boolean[][] visited;
static boolean[][] isAttacked;
static int tCnt; // 남은 포탑 개수
static List<Tower> towerList;
static Point[][] route;
static int[] dx = {0, 1, 0, -1}; // 우, 하, 좌, 상
static int[] dy = {1, 0, -1, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new Tower[N][M];
towerList = new ArrayList<>();
// 타워
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
int power = Integer.parseInt(st.nextToken());
map[i][j] = new Tower(i, j, power, 0);
}
}
// 시뮬
for(int turn=1; turn<=K; turn++) {
// 남은 포탑이 1개면 즉시 중단
init();
if(tCnt <= 1) break;
sortTower();
// 1. 공격자 선정
Tower start = getAttack();
start.power += (N+M); // 공격력 강화
start.time = turn;
// 2. 공격대상 선정
Tower target = getTarget();
// 3. 공격
isAttacked = new boolean[N][M];
isAttacked[start.x][start.y] = true;
isAttacked[target.x][target.y] = true;
if(!laser(start, target)) {
bomb(start, target);
}
// 4. 포탑 부서짐
breakTower();
// 5. 포탑 정비
fixTower();
}
// 결과 출력
int max = Integer.MIN_VALUE;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
max = Math.max(map[i][j].power, max);
}
}
System.out.println(max);
}
public static void init() {
tCnt = 0;
towerList.clear();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j].power > 0) {
towerList.add(map[i][j]);
tCnt++;
}
}
}
}
public static Tower getAttack() {
return towerList.get(0);
}
public static Tower getTarget() {
return towerList.get(tCnt-1);
}
public static void sortTower() {
Collections.sort(towerList);
}
public static boolean laser(Tower start, Tower target) {
boolean flag = false;
Queue<Point> q = new ArrayDeque<>();
visited = new boolean[N][M];
route = new Point[N][M];
q.offer(new Point(start.x, start.y));
visited[start.x][start.y] = true;
Point cur;
while(!q.isEmpty()) {
cur = q.poll();
// target에 도착했을 때
if(cur.x == target.x && cur.y == target.y) {
flag = true;
break;
}
for(int i=0; i<4; i++) {
int nx = (cur.x + dx[i] + N) % N;
int ny = (cur.y + dy[i] + M) % M;
if(map[nx][ny].power == 0 || visited[nx][ny]) continue;
route[nx][ny] = new Point(cur.x, cur.y);
q.offer(new Point(nx, ny));
visited[nx][ny] = true;
}
}
if(flag) {
// 레이저 공격
// 1. target 공격
map[target.x][target.y].power -= start.power;
// 2. 경로에 있는 포탑 공격
cur = route[target.x][target.y];
int p = start.power/2;
while(cur.x != start.x || cur.y != start.y) {
isAttacked[cur.x][cur.y] = true;
map[cur.x][cur.y].power -= p;
cur = route[cur.x][cur.y];
}
}
return flag;
}
public static void bomb(Tower start, Tower target) {
int[] tx = {0, 0, -1, -1, -1, 1, 1, 1};
int[] ty = {-1, 1, -1, 0, 1, -1, 0, 1};
target.power -= start.power;
int p = start.power / 2;
for(int i=0; i<8; i++) {
int nx = (target.x + tx[i] + N) % N;
int ny = (target.y + ty[i] + M) % M;
if(map[nx][ny].power == 0) continue;
if(nx == start.x && ny == start.y) continue;
isAttacked[nx][ny] = true;
map[nx][ny].power -= p;
}
}
public static void breakTower() {
tCnt = 0;
towerList.clear();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j].power < 0) {
map[i][j].power = 0;
}
}
}
}
public static void fixTower() {
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j].power == 0 || isAttacked[i][j]) continue;
map[i][j].power++;
}
}
}
// 디버깅용
public static void print() {
StringBuilder sb = new StringBuilder();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
sb.append(map[i][j].power + " ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}
'알고리즘 > 코드트리' 카테고리의 다른 글
[코드트리] 싸움땅 - JAVA (0) | 2024.06.07 |
---|---|
[코드트리] 팩맨 - JAVA (0) | 2024.06.02 |
[코드트리] 메이즈 러너 - JAVA (0) | 2024.04.12 |
[코드트리] 왕실의 기사 대결 - JAVA (0) | 2024.04.11 |