Notice
Recent Posts
Recent Comments
Link
S E P H ' S
[Java] 포탑부수기 본문
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
최고의 알고리즘 전문가들이 체계적인 코딩테스트 문제 유형 분류와 학습 커리큘럼을 제시합니다. 알고리즘 학습의 A to Z를 경험해보세요!
www.codetree.ai
문제 풀이
조건에 맞춰서 차근차근히 풀어나가면 되는 구현 문제이다. 고려해야할 것이 많아서 처음 설계를 할 때 꼼꼼히 따져봐야한다. 문제를 풀어나가는 핵심 순서는 다음과 같다.
1. K번 동안 로직을 반복. 포탑이 한개만 남게 된다면 반복횟수가 K번이 되지 않았더라도 그 포탑의 공격력을 정답으로 하고 종료.
2. 가장 약한 포탑 선정
2-1. 가장 약한 포탑이 공격자이므로 턴을 저장.
2-2. 가장 약한 포탑의 공격력을 N + M 만큼 증가.
3. 가장 강한 포탑 선정
4. 레이저 공격이 가능한지 판단. 불가능하다면 폭탄 범위 공격.
5. 파괴된 포탑 처리.
6. 공격과 관련없는 포탑은 공격력 1씩 증가.
가장 신경 써야 했던 로직은 세가지가 있다. 첫번째는 가장 약한, 강한 포탑의 선정(포탑의 우선순위 정하기). 두번째는 레이저 공격이 가능한지 판단하는 것(최단경로 구하기), 세번째는 좌표가 board의 범위를 벗어나면 방문이 불가한 것이 아닌 반대쪽 좌표로 이동할 수 있다는 것(범위를 벗어났을때 좌표 처리)이었다.
포탑 우선순위 정하기 (1)
먼저, 포탑의 우선순위를 정하는데 있어서 참고한 풀이 중 신선한 충격을 주었던 방법이 있어서 가져와봤다. 우선 문제의 조건에서 가장 약한 포탑을 고르는 우선순위 조건을 확인해보자. (가장 강한 포탑은 반대이므로 따로 확인은 하지 않겠다.)
1. 공격력이 가장 낮은 포탑이 가장 약한 포탑이다.
2. 만약 공격력이 가장 낮은 포탑이 2개 이상이라면, 가장 최근에 공격한 포탑이 가장 약한 포탑이다.
3. 만약 2번과 같은 포탑이 2개 이상이라면, 각 포탑 위치의 행과 열의 합이 가장 큰 포탑이 가장 약한 포탑이다.
4. 만약 3번과 같은 포탑이 2개 이상이라면, 각 포탑 위치의 열 값이 가장 큰 포탑이 가장 약한 포탑이다.
가져온 풀이는 3번과 4번 조건에 집중해서 나온 방법이다. 행과 열의 합이 가장 크고 그러한 것이 여러개라면 열 값이 가장 큰 포탑이 가장 약한 포탑이라고 하고 있다. 먼저 4 x 4 배열 그림을 예시로 보도록 하겠다. 다음 그림에서 나타내는 배열의 각 값들은 행과 열의 합이다.
어느정도 감이 올 것이다. 다음 그림을 본다면 더 확실하게 어떤 방법을 쓰게 되는지 감이 잡힐 것이다.
행과 열 값이 큰 포탑, 그 다음 열 값이 큰 포탑이라는 조건을 생각하고 그림 2를 보면 2차원 배열을 맨 우측 아래 값부터 오른쪽에서 왼쪽을 향하는 대각선으로 탐색해 나가면 해당 조건에 딱 맞게 값을 탐색할 수 있음을 알 수 있다. (2, 3) 과 (3, 2)를 보면 열 값이 3인 부분부터 탐색하고 있다. 이를 코드로 구현해보면 다음과 같다.
for (int sum = N + M - 2; sum > -1; sum--) {
for (int j = M - 1; j > -1; j--) {
int i = sum - j;
// 범위를 벗어나면 continue
// 무너진 포탑이면 continue
if (i < 0 || i >= N) continue;
if (board[i][j] == 0) continue;
// 공격력과 턴을 갱신
if (minValue > board[i][j]) {
minValue = board[i][j];
maxTurn = lastAttack[i][j];
minI = i;
minJ = j;
} else if (minValue == board[i][j] && maxTurn < lastAttack[i][j]) {
minValue = board[i][j];
maxTurn = lastAttack[i][j];
minI = i;
minJ = j;
}
}
// 가장 약한 포탑 좌표 저장
attacker[0] = minI;
attacker[1] = minJ;
}
좌표의 최대값은 각각 N-1, M-1이므로 행과 열의 합의 최대값은 N + M - 2가 되고 최솟값은 0이 되고 열의 최대값은 M-1이고 최솟값은 0이다. 행은 sum 에서 j를 뺀값이 된다. 이렇게 범위를 벗어나거나 무너진 포탑은 넘어가고 board를 탐색하면서 공격력과 턴이 조건에 맞게 갱신이 되면 최종적으로 나온 좌표값을 저장하면 된다. 이런 생각을 한다는게 굉장히 기발했다.
포탑 우선순위 정하기 (2)
보통 많이 떠올리게 되는 Comparable을 사용하는 방법이다. Turret이라는 클래스를 만들어 조건에 맞게 Comparable의 compareTo 메소드를 완성시키면 된다. Turret 클래스를 만들어 사용하게 되면 우선순위 큐에서 뽑아 나가거나 리스트를 사용하여 정렬하는 방법 두 가지를 생각해볼 수 있다. 다만 우선순위 큐를 활용하는 방법은 주의해야할 것이 있다. 이 문제에서는 가장 약한 포탑, 가장 강한 포탑 두 가지의 정보만 필요하고 문제 조건에서 포탑이 하나만 남게 되면 종료하도록 되어있기 때문에 로직을 반복하면서 우선순위 큐가 비어있게 될 경우가 없다. 그러나 다른 문제에서 우선순위 큐와 같은 자료구조를 사용하게 되면 반복하면서 큐가 비어있게 될 경우를 생각해보고 선택해야할 것이다. Turret 클래스의 코드는 다음과 같다.
static class Turret implements Comparable<Turret> {
int x, y, power, turn;
public Turret(int x, int y, int power, int turn) {
this.x = x;
this.y = y;
this.power = power;
this.turn = turn;
}
@Override
public int compareTo(Turret o) {
if (this.power != o.power) return this.power - o.power;
if (this.turn != o.power) return o.turn - this.turn;
if ((this.x + this.y) != (o.x + o.y)) return (o.x + o.y) - (this.x + this.y);
return o.y - this.y;
}
}
범위를 벗어난 좌표처리
보통의 구현문제들은 범위를 벗어난 좌표 처리는 진행하지 않도록 했었다. 이 문제에서는 범위를 벗어나는 것이 아니라 반대편 좌표로 이동하도록 되어있다. 또한 폭탄으로 범위공격을 하는 경우에도 동일하게 작동해야 한다. 여기서 필자는 처음 풀이 했을 때는 if ~ else if 를 사용하여 x, y 좌표 모두 범위를 넘어가는 경우를 제대로 해주지 못했었다. 주의하여 코드를 작성해주어야 한다. 코드는 다음과 같다.
// nx, ny (x, y의 다음좌표)
if (0 < nx) nx = N - 1;
if (nx >= N) nx = 0;
if (0 < ny) ny = M - 1;
if (ny >= M) ny = 0;최단경로 구하기
문제 조건에서 레이저 공격은 방향의 우선순위에 맞게 공격 대상으로 도달할 수 있으면 레이저 공격으로 공격한다. 이것이 불가능하면 폭탄 공격을 하게 되는데 이것이 의미하는 것은 공격자로부터 공격대상까지의 최단경로를 구해야한다. 또한 레이저 공격이 가능하다면 해당 경로에 위치해있던 포탑들도 공격을 받아 상태를 변화시켜야 하기 때문에 경로에 위치해있던 포탑들의 위치를 담을 것들도 필요하다. 그래서 레이저 공격에 대한 결과를 실행하기 전에 BFS가 마무리된 후, 공격대상에 방문하지 않았다면 false를 리턴하도록 했다. 그런 다음, 공격대상의 좌표로부터 시작하여 이전 좌표로 이동해가면서 공격 여부, 공격력 감소 부분을 처리했다.
메인은 BFS를 실행하고 신경써야할 정보는 현재 좌표로 도달하기 전의 좌표, 해당 좌표의 방문 여부이다. 구현 여부에 따라서 다른 방법을 사용할 수도 있지만 필자는 좌표마다 이전 좌표를 저장하는 2차원 배열을 사용했다. 코드는 다음과 같다.
static boolean possibleLazer() {
// 우 하 좌 상
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
Queue<Path> q = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
Path[][] prev = new Path[N][M];
q.add(new Path(attacker.x, attacker.y));
visited[attacker.x][attacker.y] = true;
isAttacked[attacker.x][attacker.y] = true;
while(!q.isEmpty()) {
Path cur = q.poll();
int cx = cur.x;
int cy = cur.y;
for (int d = 0; d < 4; d++) {
int nx = cx + dx[d];
int ny = cy + dy[d];
// 끝 지점에 도달하면 반대쪽 처음으로 돌아간다.
if (nx < 0) nx = N - 1;
if (nx >= N) nx = 0;
if (ny < 0) ny = M - 1;
if (ny >= M) ny = 0;
if (visited[nx][ny] || board[nx][ny] == null) continue;
Path nextPath = new Path(nx, ny);
q.add(nextPath);
visited[nx][ny] = true;
prev[nx][ny] = cur;
}
}
if (!visited[target.x][target.y]) return false;
Path back = new Path(target.x, target.y);
while (back.x != attacker.x || back.y != attacker.y) {
int power = attacker.power / 2;
if (back.x == target.x && back.y == target.y) {
power = attacker.power;
}
attack(back.x, back.y, power);
back = prev[back.x][back.y];
}
return true;
}
전체코드
1. 2차원 배열 대각선 탐색
더보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int[] ans;
// 보드 정보
static int[][] board;
// 이번 턴에 공격과 관련이 있었는가?
static boolean[][] isAttacked;
// 마지막에 공격한 턴은 언제인가?
static int[][] lastAttack;
public static void main(String[] args) throws Exception {
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());
board = new int[N][M];
lastAttack = new int[N][M];
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());
board[i][j] = power;
}
}
progress();
System.out.println(board[ans[0]][ans[1]]);
}
static void progress() {
for (int turn = 1; turn < K + 1; turn++) {
if (isFinish()) {
break;
}
int[] attacker = selectAttacker(); // 가장 약한 포탑 선정
int[] target = selectTarget(); // 가장 강한 포탑 선정
isAttacked = new boolean[N][M]; // 공격당한 좌표를 위한 boolean 2차원 배열 생성
board[attacker[0]][attacker[1]] += (N + M); // 공격 포탑의 공격력을 N + M 만큼 증가
lastAttack[attacker[0]][attacker[1]] = turn; // 공격 포탑의 최근 공격 턴을 기록
isAttacked[attacker[0]][attacker[1]] = true; // 공격과 관련되었으므로 true 로 기록
if (!possibleLaser(attacker, target)) { // 레이저 공격이 가능한지 판단하고 불가하다면 폭탄으로 공격
bomb(attacker, target);
}
for (int i = 0; i < N; i++) { // 공격받지 않았고 0(무너짐) 이 아니면 1씩 증가
for (int j = 0; j < M; j++) {
if (!isAttacked[i][j] && board[i][j] != 0) {
board[i][j]++;
}
}
}
}
ans = selectTarget();
}
static int[] selectAttacker() {
int[] attacker = new int[2];
int minValue = Integer.MAX_VALUE;
int maxTurn = -1;
int minX = 0;
int minY = 0;
for (int sum = N + M - 2; sum > -1; sum--) {
for (int j = M - 1; j > -1; j--) {
int i = sum - j;
if (i < 0 || i >= N) continue;
if (board[i][j] == 0) continue;
if (minValue > board[i][j]) {
minValue = board[i][j];
maxTurn = lastAttack[i][j];
minX = i;
minY = j;
} else if (minValue == board[i][j] && maxTurn < lastAttack[i][j]) {
minValue = board[i][j];
maxTurn = lastAttack[i][j];
minX = i;
minY = j;
}
}
}
attacker[0] = minX;
attacker[1] = minY;
return attacker;
}
static int[] selectTarget() {
int[] target = new int[2];
int maxValue = -1;
int minTurn = Integer.MAX_VALUE;
int maxX = 0;
int maxY = 0;
for (int sum = 0; sum < N + M - 1; sum++) {
for (int j = 0; j < M; j++) {
int i = sum - j;
if (i < 0 || i >= N) continue;
if (board[i][j] == 0) continue;
if (maxValue < board[i][j]) {
maxValue = board[i][j];
minTurn = lastAttack[i][j];
maxX = i;
maxY = j;
} else if (maxValue == board[i][j] && minTurn > lastAttack[i][j]) {
maxValue = board[i][j];
minTurn = lastAttack[i][j];
maxX = i;
maxY = j;
}
}
}
target[0] = maxX;
target[1] = maxY;
return target;
}
static boolean possibleLaser(int[] attacker, int[] target) {
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
int[][][] come = new int[N][M][2]; // x행 y열이 어디로부터 왔는가? 0 : x, 1: y
// 우하좌상
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
q.add(attacker);
visited[attacker[0]][attacker[1]] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0];
int y = cur[1];
for (int d = 0; d < 4; d++) {
int nx = (x + dx[d] + N) % N;
int ny = (y + dy[d] + M) % M;
if (visited[nx][ny]) continue;
if (board[nx][ny] == 0) continue;
come[nx][ny][0] = x;
come[nx][ny][1] = y;
visited[nx][ny] = true;
q.add(new int[]{nx, ny});
}
}
if (!visited[target[0]][target[1]]) return false;
int[] back = target;
while (back[0] != attacker[0] || back[1] != attacker[1]) {
int power = board[attacker[0]][attacker[1]] / 2;
if (back[0] == target[0] && back[1] == target[1]) {
power = board[attacker[0]][attacker[1]];
}
board[back[0]][back[1]] = attack(back[0], back[1], power);
back = come[back[0]][back[1]];
}
return true;
}
static int attack(int x, int y, int power) {
isAttacked[x][y] = true;
board[x][y] = Math.max(0, board[x][y] - power);
return board[x][y];
}
static void bomb(int[] attacker, int[] target) {
int[] dx = {0, -1, 0, 1, 0, -1, -1, 1, 1};
int[] dy = {0, 0, 1, 0, -1, -1, 1, -1, 1};
for (int d = 0; d < 9; d++) {
int nx = (target[0] + dx[d] + N) % N;
int ny = (target[1] + dy[d] + M) % M;
if (nx == attacker[0] && ny == attacker[1]) continue;
int power = board[attacker[0]][attacker[1]] / 2;
if (nx == target[0] && ny == target[1]) power = board[attacker[0]][attacker[1]];
board[nx][ny] = attack(nx, ny, power);
}
}
// 보드에서 포탑이 한개만 남으면 종료이므로 cnt == 1이 true 이도록 반환
static boolean isFinish() {
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] != 0) cnt++;
}
}
return cnt == 1;
}
}
2. 우선순위 큐 사용
더보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int answer;
static int N, M, K;
static PriorityQueue<Turret> pq;
static Turret[][] board;
static boolean[][] isAttacked;
static Turret attacker;
static Turret target;
public static void main(String[] args) throws Exception {
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());
board = new Turret[N][M];
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());
if (power > 0) {
board[i][j] = new Turret(i, j, power, 0);
}
}
}
progress();
System.out.println(answer);
}
static void progress() {
for (int k = 1; k <= K; k++) {
// 가장 약한 포탑, 강한 포탑을 뽑기 위해 turretList 정렬
init();
// 만일 turretList.size() 가 1 이라면 종료하고 그 타워의 파워를 정답으로 출력
if (pq.size() == 1) {
answer = pq.poll().power;
break;
}
// 가장 약한 포탑 선정 -> 얘가 공격을 하기 때문에 현재 K 값을 turn 으로 넣어준다.
// 가장 강한 포탑 선정
attacker = pq.poll();
target = selectStrongestTurret();
attacker.turn = k;
attacker.power += (N + M);
// 공격 단계 -> 공격 경로에 있거나 범위에 있는 포탑들은 isAttacked 에 true 처리
// 레이저로 공격 가능한지 판단
// 레이저 공격
// 포탑 공격
if (!possibleLazer()) {
attackBomb();
}
// 공격을 받아 power 가 0 이하인 포탑들은 0 처리
// 공격과 무관한 포탑들은 power 1 증가
repair();
}
// 가장 강한 포탑 power 찾아 정답으로 출력
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] != null) {
answer = Math.max(answer, board[i][j].power);
}
}
}
}
static Turret selectStrongestTurret() {
Turret t = null;
while(!pq.isEmpty()) {
t = pq.poll();
}
return t;
}
static void repair() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] != null && !isAttacked[i][j]) board[i][j].power++;
}
}
}
static void attackBomb() {
int[] dx = {0, -1, 0, 1, 0, -1, -1, 1, 1};
int[] dy = {0, 0, 1, 0, -1, -1, 1, -1, 1};
for (int d = 0; d < 9; d++) {
int nx = target.x + dx[d];
int ny = target.y + dy[d];
// 끝 지점에 도달하면 반대쪽 처음으로 돌아간다.
if (nx < 0) nx = N - 1;
if (nx >= N) nx = 0;
if (ny < 0) ny = M - 1;
if (ny >= M) ny = 0;
if (board[nx][ny] == null) continue;
if (nx == attacker.x && ny == attacker.y) continue;
isAttacked[nx][ny] = true;
int power = attacker.power / 2;
if (nx == target.x && ny == target.y) {
power = attacker.power;
}
attack(nx, ny, power);
}
}
// 레이저로 공격 가능한지 판단
static boolean possibleLazer() {
// 우 하 좌 상
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
Queue<Path> q = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
Path[][] prev = new Path[N][M];
q.add(new Path(attacker.x, attacker.y));
visited[attacker.x][attacker.y] = true;
isAttacked[attacker.x][attacker.y] = true;
while(!q.isEmpty()) {
Path cur = q.poll();
int cx = cur.x;
int cy = cur.y;
for (int d = 0; d < 4; d++) {
int nx = cx + dx[d];
int ny = cy + dy[d];
// 끝 지점에 도달하면 반대쪽 처음으로 돌아간다.
if (nx < 0) nx = N - 1;
if (nx >= N) nx = 0;
if (ny < 0) ny = M - 1;
if (ny >= M) ny = 0;
if (visited[nx][ny] || board[nx][ny] == null) continue;
Path nextPath = new Path(nx, ny);
q.add(nextPath);
visited[nx][ny] = true;
prev[nx][ny] = cur;
}
}
if (!visited[target.x][target.y]) return false;
Path back = new Path(target.x, target.y);
while (back.x != attacker.x || back.y != attacker.y) {
int power = attacker.power / 2;
if (back.x == target.x && back.y == target.y) {
power = attacker.power;
}
attack(back.x, back.y, power);
back = prev[back.x][back.y];
}
return true;
}
static void attack(int x, int y, int power) {
isAttacked[x][y] = true;
board[x][y].power = Math.max(0, board[x][y].power - power);
if (board[x][y].power == 0) board[x][y] = null;
}
// 가장 약한 포탑, 강한 포탑을 뽑기 위해 PriorityQueue 와 공격받은 정보 새로 생성.
static void init() {
pq = new PriorityQueue<>();
isAttacked = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] != null) pq.add(board[i][j]);
}
}
}
static class Path {
int x, y;
public Path(int x, int y) {
this.x = x;
this.y = y;
}
}
static class Turret implements Comparable<Turret> {
int x, y, power, turn;
public Turret(int x, int y, int power, int turn) {
this.x = x;
this.y = y;
this.power = power;
this.turn = turn;
}
@Override
public int compareTo(Turret o) {
if (this.power != o.power) return this.power - o.power;
if (this.turn != o.turn) return o.turn - this.turn;
if ((this.x + this.y) != (o.x + o.y)) return (o.x + o.y) - (this.x + this.y);
return o.y - this.y;
}
}
}
3. 리스트 사용
더보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int answer;
static int N, M, K;
static List<Turret> turretList;
static Turret[][] board;
static boolean[][] isAttacked;
static Turret attacker;
static Turret target;
public static void main(String[] args) throws Exception {
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());
board = new Turret[N][M];
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());
if (power > 0) {
board[i][j] = new Turret(i, j, power, 0);
}
}
}
progress();
System.out.println(answer);
}
static void progress() {
for (int k = 1; k <= K; k++) {
// 가장 약한 포탑, 강한 포탑을 뽑기 위해 turretList 정렬
init();
// 만일 turretList.size() 가 1 이라면 종료하고 그 타워의 파워를 정답으로 출력
if (turretList.size() == 1) {
answer = turretList.get(0).power;
break;
}
// 가장 약한 포탑 선정 -> 얘가 공격을 하기 때문에 현재 K 값을 turn 으로 넣어준다.
// 가장 강한 포탑 선정
attacker = turretList.get(0);
target = turretList.get(turretList.size() - 1);
attacker.turn = k;
attacker.power += (N + M);
// 공격 단계 -> 공격 경로에 있거나 범위에 있는 포탑들은 isAttacked 에 true 처리
// 레이저로 공격 가능한지 판단
// 레이저 공격
// 포탑 공격
if (!possibleLazer()) {
attackBomb();
}
// 공격을 받아 power 가 0 이하인 포탑들은 0 처리
// 공격과 무관한 포탑들은 power 1 증가
repair();
}
// 가장 강한 포탑 power 찾아 정답으로 출력
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] != null) {
answer = Math.max(answer, board[i][j].power);
}
}
}
}
static void repair() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] != null && !isAttacked[i][j]) board[i][j].power++;
}
}
}
static void attackBomb() {
int[] dx = {0, -1, 0, 1, 0, -1, -1, 1, 1};
int[] dy = {0, 0, 1, 0, -1, -1, 1, -1, 1};
for (int d = 0; d < 9; d++) {
int nx = target.x + dx[d];
int ny = target.y + dy[d];
// 끝 지점에 도달하면 반대쪽 처음으로 돌아간다.
if (nx < 0) nx = N - 1;
if (nx >= N) nx = 0;
if (ny < 0) ny = M - 1;
if (ny >= M) ny = 0;
if (board[nx][ny] == null) continue;
if (nx == attacker.x && ny == attacker.y) continue;
isAttacked[nx][ny] = true;
int power = attacker.power / 2;
if (nx == target.x && ny == target.y) {
power = attacker.power;
}
attack(nx, ny, power);
}
}
// 레이저로 공격 가능한지 판단
static boolean possibleLazer() {
// 우 하 좌 상
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
Queue<Path> q = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
Path[][] prev = new Path[N][M];
q.add(new Path(attacker.x, attacker.y));
visited[attacker.x][attacker.y] = true;
isAttacked[attacker.x][attacker.y] = true;
while(!q.isEmpty()) {
Path cur = q.poll();
int cx = cur.x;
int cy = cur.y;
for (int d = 0; d < 4; d++) {
int nx = cx + dx[d];
int ny = cy + dy[d];
// 끝 지점에 도달하면 반대쪽 처음으로 돌아간다.
if (nx < 0) nx = N - 1;
if (nx >= N) nx = 0;
if (ny < 0) ny = M - 1;
if (ny >= M) ny = 0;
if (visited[nx][ny] || board[nx][ny] == null) continue;
Path nextPath = new Path(nx, ny);
q.add(nextPath);
visited[nx][ny] = true;
prev[nx][ny] = cur;
}
}
if (!visited[target.x][target.y]) return false;
Path back = new Path(target.x, target.y);
while (back.x != attacker.x || back.y != attacker.y) {
int power = attacker.power / 2;
if (back.x == target.x && back.y == target.y) {
power = attacker.power;
}
attack(back.x, back.y, power);
back = prev[back.x][back.y];
}
return true;
}
static void attack(int x, int y, int power) {
isAttacked[x][y] = true;
board[x][y].power = Math.max(0, board[x][y].power - power);
if (board[x][y].power == 0) board[x][y] = null;
}
// 가장 약한 포탑, 강한 포탑을 뽑기 위해 turretList 정렬
static void init() {
turretList = new ArrayList<>();
isAttacked = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] != null) turretList.add(board[i][j]);
}
}
Collections.sort(turretList);
}
static class Path {
int x, y;
public Path(int x, int y) {
this.x = x;
this.y = y;
}
}
static class Turret implements Comparable<Turret> {
int x, y, power, turn;
public Turret(int x, int y, int power, int turn) {
this.x = x;
this.y = y;
this.power = power;
this.turn = turn;
}
@Override
public int compareTo(Turret o) {
if (this.power != o.power) return this.power - o.power;
if (this.turn != o.turn) return o.turn - this.turn;
if ((this.x + this.y) != (o.x + o.y)) return (o.x + o.y) - (this.x + this.y);
return o.y - this.y;
}
}
}
정리
문제의 조건을 정말 꼼꼼히 확인하고 어떤 자료구조로 구현할 것인지 정한 다음 차례대로 구현만 해나가면 되는 문제이다. 물론 풀고나면 항상 별로 어렵지 않다. 구현은 정말 경험치와 꼼꼼함이 중요한것 같다.