문제
입력
첫 번째 줄에 N, M, K가 공백을 사이에 두고 주어집니다.
두 번째 줄부터 N개의 줄에 걸쳐서 N×M 격자에 대한 정보가 주어집니다.
출력
첫 번째 줄에 K번의 턴이 종료된 후 남아있는 포탑 중 가장 강한 포탑의 공격력을 출력합니다.
풀이
제한조건
- 4≤N,M≤10
- 1≤K≤1,000
- 0≤공격력≤5,000
접근방법
시뮬레이션
항상 침착하게 주어진대로 구현하자.
크게 4가지의 기능을 구현하면 된다.
1. 공격 포탑 선정
2. 피해 포탑 선정
3. 공격
4. 회복0. 구성
각각의 자리에 포탑을 모두 만들었다.
편의상 index 번호로 관리하기로 하였다.
2 x 5크기의 입력
0 1 2 3 4
5 6 7 8 9
3 x 2크기의 입력
0 1
2 3
4 5
와 같은 방식N x M크기의 입력에 대해서 좌상단부터 순차적으로 위치에 대한 번호를 부여했다.
1. 공격 포탑 선정
가장 약한 포탑이 공격 포탑이 된다.
공격 포탑은 N+M의 공격력을 추가로 제공받는다.
선정기준은 아래를 따른다.
1. 공격력이 가장 낮은 포탑이 가장 약한 포탑입니다.
2. 만약 공격력이 가장 낮은 포탑이 2개 이상이라면, 가장 최근에 공격한 포탑이 가장 약한 포탑입니다. (모든 포탑은 시점 0에 모두 공격한 경험이 있다고 가정하겠습니다.)
3. 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 행과 열의 합이 가장 큰 포탑이 가장 약한 포탑입니다.
4. 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 열 값이 가장 큰 포탑이 가장 약한 포탑입니다.또한 아래에서 서술한 피해 포탑 선정은 공격 포탑 선정의 정확히 반대이다.
따라서, 우리는 포탑을 정렬하게 된다면, 가장 첫번째와 마지막 원소가 각각 공격/피해 포탑임을 알 수 있다.
static class Tower implements Comparable<Tower> {
int idx;
int power;
int lastAttack;
int x;
int y;
public Tower(int idx, int power, int lastAttack, int x, int y) {
this.idx = idx;
this.power = power;
this.lastAttack = lastAttack;
this.x = x;
this.y = y;
}
public int compareTo(Tower o) {
if (this.power != o.power)
return this.power - o.power;
if (this.lastAttack != o.lastAttack)
return o.lastAttack - this.lastAttack;
if (this.x + this.y != o.x + o.y)
return (o.x + o.y) - (this.x + this.y);
return o.y - this.y;
}
}2. 피해 포탑 선정
1에서 서술한것 처럼, 정렬을 통해 한번에 구할 수 있다.
정렬을 이용하지 않았다면, 이중 For문을 통해 직접 공격/피해 포탑을 찾아주자.
3. 공격
공격에는 2가지 방식이 존재한다.
1. 레이저
2. 포탄
레이저 공격의 경우, BFS를 통해 탐색을 하며 최단거리로 피해포탑에 도달 할 수 있는지 체크해 주자.
이때 visit 배열에는 이전에 어디서 왔는지에 대한 정보를 저장해주면, 피해포탑에서 역추적하며 찾아갈 수 있다.
포탄의 경우는 훨씬 간단하다.
피해 포탑의 8가지 인접 방향을 모두 찾아주면 된다.
4. 회복
3번 을 구현하는 과정에서 별도의 배열을 하나 생성해두고,
특정 위치의 포탑이 공격받았으면, 상태값을 true로 변경해주자.
여기서는 전체 포탑을 순회하며
- 포탑이 부서지지 않았으며
- 최근에 공격 또는 피해를 받지 않았다면
체력을 증가시켜 준다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
public class Main {
static class Tower implements Comparable<Tower> {
int idx;
int power;
int lastAttack;
int x;
int y;
public Tower(int idx, int power, int lastAttack, int x, int y) {
this.idx = idx;
this.power = power;
this.lastAttack = lastAttack;
this.x = x;
this.y = y;
}
@Override
public int compareTo(Tower o) {
if (this.power != o.power)
return this.power - o.power;
if (this.lastAttack != o.lastAttack)
return o.lastAttack - this.lastAttack;
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 int attacker, receiver;
static boolean[] recent;
static Tower[] towers;
public static void main(String[] args) throws Exception {
// input
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = in.readLine().split(" ");
N = stoi(inputs[0]);
M = stoi(inputs[1]);
K = stoi(inputs[2]);
towers = new Tower[N * M];
for (int i = 0; i < N; ++i) {
inputs = in.readLine().split(" ");
for (int j = 0; j < M; ++j) {
int pos = i * M + j;
towers[pos] = new Tower(pos, stoi(inputs[j]), 0, i, j);
}
}
for (int t = 0; t < K; ++t) {
recent = new boolean[N * M];
List<Tower> towerList = new ArrayList<>();
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
int pos = i * M + j;
if (towers[pos].power > 0)
towerList.add(towers[pos]);
}
}
// 남은 타워가 1개 -> 종료
if (towerList.size() <= 1)
break;
Collections.sort(towerList);
// Step1. 공격자 선정
attacker = towerList.get(0).idx;
recent[attacker] = true;
towers[attacker].lastAttack = t + 1;
towers[attacker].power += (N + M);
// Step2. 공격자의 공격
// Step3. 포탑 부서짐
receiver = towerList.get(towerList.size() - 1).idx;
recent[receiver] = true;
Attack();
// Step4. 포탑 정비
repairTower();
}
// 남아 있는 포탑 중 가장 강한 포탑의 공격력 출력
int max = -1;
for (Tower t : towers)
max = Math.max(max, t.power);
System.out.println(max);
}
static int[] dx = {0, 1, 0, -1, -1, 1, 1, -1};
static int[] dy = {1, 0, -1, 0, 1, 1, -1, -1};
private static void Attack() {
boolean flag = false;
// 레이저 공격 시도
int[] visit = new int[N * M];
Arrays.fill(visit, -1);
visit[attacker] = attacker;
Queue<Integer> q = new ArrayDeque<>();
q.add(attacker);
while (!q.isEmpty()) {
int cur = q.poll();
int x = cur / M;
int y = cur % M;
if (cur == receiver) {
flag = true;
break;
}
for (int d = 0; d < 4; ++d) {
int next = getNext(x, y, d);
// 이미 방문한적이 있다.
if (visit[next] != -1)
continue;
// 파괴된 자리는 이동하지 않는다.
if (towers[next].power <= 0)
continue;
int nx = next / M;
int ny = next % M;
visit[next] = cur;
q.add(next);
}
}
// 레이저로 공격했다면 종료.
if (flag) {
int start = visit[receiver];
while (start != attacker) {
recent[start] = true;
towers[start].power -= (towers[attacker].power / 2);
if(start == attacker)
break;
start = visit[start];
}
towers[receiver].power -= towers[attacker].power;
return;
}
// 포탄 공격 시도
for (int d = 0; d < 8; ++d) {
int next = getNext(receiver / M, receiver % M, d);
// 파괴된 포탑은 피해를 입지 않음.
if (towers[next].power == 0)
continue;
// 공격자는 피해를 입지 않는다.
if (next == attacker)
continue;
recent[next] = true;
towers[next].power -= (towers[attacker].power / 2);
}
towers[receiver].power -= towers[attacker].power;
}
private static int getNext(int x, int y, int d) {
int nx = (x + dx[d] + N) % N;
int ny = (y + dy[d] + M) % M;
return (nx * M) + ny;
}
private static void repairTower() {
for (int i = 0; i < N * M; ++i) {
// 이미 파괴된 포탑
if (towers[i].power < 1)
continue;
// 최근 공격 또는 피해를 받음
if (recent[i])
continue;
towers[i].power++;
}
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}