문제 이해
문제 자체는 시뮬레이션이므로 문제의 조건을 놓치지 않고 잘 따라가면 될 것이라 생각하며 풀었습니다.
접근 방법
- 골렘 이동
- 이미 숲의 최상단까지 골렘이 있어서 이번 골렘이 들어가지도 못하는 경우가 있을 수 있습니다. 저는 0행부터 사용하도록 구현했기 때문에 현재 골렘의 행 좌표가 -2일 떄와 -1일 때 맵 체크 조건을 다르게 하지 않으면
ArrayIndexOutOfBoundsException가 발생합니다. 이를 주의해야 했습니다. - 왼쪽 또는 오른쪽으로 이동할 때 단순히 대각선으로 움직이는 것이 아니라 ‘왼쪽으로 한 칸 움직인 후 아래로 한 칸’ 이동합니다. 그래서 대각선 아래의 두 칸만 확인하는 것이 아니라 최대 네 칸이 비어있는지 확인해야 합니다.
- 만약 골렘이 멈췄을 때 한 칸이라도 숲 밖에 있다면 모든 골렘을 지우고 점수도 얻지 못하는 것을 고려해야 합니다.
- 이미 숲의 최상단까지 골렘이 있어서 이번 골렘이 들어가지도 못하는 경우가 있을 수 있습니다. 저는 0행부터 사용하도록 구현했기 때문에 현재 골렘의 행 좌표가 -2일 떄와 -1일 때 맵 체크 조건을 다르게 하지 않으면
- 정령 이동
- 일반적인 맵 탐색 문제의 경우 모든 갈 수 있는 칸을 한 칸씩 이동하지만, 이 문제에서는 (1) 현재 골렘의 가장 남쪽 칸과 (2) 출구에서 갈 수 있는 다음 골렘만 찾으면 될거라고 생각했습니다.
- 탐색할 위치 좌표가 매우 많이 바뀌어야 하기 때문에 인덱스 수정에 주의가 필요합니다.
코드
1public class Main {
2
3 static int R, C, K, score, rMax;
4 static int[][] m, gArr;
5 static int[] di = {-1, 0, 1, 0}, dj = {0, 1, 0, -1};
6 static boolean[] v;
7
8 public static void main(String[] args) throws Exception {
9 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
10
11 StringTokenizer st = new StringTokenizer(br.readLine());
12 R = Integer.parseInt(st.nextToken());
13 C = Integer.parseInt(st.nextToken());
14 K = Integer.parseInt(st.nextToken());
15
16 // initialise
17 score = 0;
18 initMap();
19 gArr = new int[K][];
20
21
22 // input K golems
23 for (int k = 0; k < K; k++) {
24 st = new StringTokenizer(br.readLine());
25 int c = Integer.parseInt(st.nextToken()) - 1;
26 int e = Integer.parseInt(st.nextToken());
27
28 // init every try
29 rMax = 0;
30 v = new boolean[K];
31 drop(k, -2, c, e);
32 }
33 System.out.println(score);
34 }
35
36 static void drop(int idx, int ci, int cj, int e) {
37 while (true) { // move until available
38 if (ci == R - 2) break; // exit at bottom
39
40 // go down
41 if ((ci == -2 && m[ci + 2][cj] == -1) || (m[ci + 2][cj] == -1 && m[ci + 1][cj - 1] == -1 && m[ci + 1][cj + 1] == -1)) {
42 ci += 1;
43 continue;
44 }
45
46 // go left
47 if (cj >= 2) {
48 if ((ci == -2 && m[ci + 2][cj - 1] == -1) || ((ci == -1) && m[ci + 2][cj - 1] == -1 && m[ci + 1][cj - 1] == -1 && m[ci + 1][cj - 2] == -1) || (m[ci + 2][cj - 1] == -1 && m[ci + 1][cj - 1] == -1 && m[ci + 1][cj - 2] == -1 && m[ci][cj - 2] == -1)) {
49 ci += 1;
50 cj -= 1;
51 e = (e + 3) % 4;
52 continue;
53 }
54 }
55
56 // go right
57 if (cj < C - 2) {
58 if ((ci == -2 && m[ci + 2][cj + 1] == -1) || ((ci == -1) && m[ci + 2][cj + 1] == -1 && m[ci + 1][cj + 1] == -1 && m[ci + 1][cj + 2] == -1) || (m[ci + 2][cj + 1] == -1 && m[ci + 1][cj + 1] == -1 && m[ci + 1][cj + 2] == -1 && m[ci][cj + 2] == -1)) {
59 ci += 1;
60 cj += 1;
61 e = (e + 1) % 4;
62 continue;
63 }
64 }
65
66 // exit when cannot go anymore
67 break;
68 }
69
70 // reset if golem located outside of the map
71 if (ci <= 0) {
72 initMap();
73 return;
74 }
75
76 // mark golem on map
77 m[ci][cj] = m[ci - 1][cj] = m[ci][cj + 1] = m[ci + 1][cj] = m[ci][cj - 1] = idx;
78 gArr[idx] = new int[] {ci, cj, e};
79
80 moveGolem(idx);
81 score += rMax;
82 }
83
84 static void moveGolem(int idx) {
85 v[idx] = true; // visited
86
87 // update rMax with the bottom of current golem
88 int ri = gArr[idx][0] + 2;
89 rMax = ri > rMax ? ri : rMax;
90
91 // exit coord of current golem
92 int e = gArr[idx][2];
93 ri = gArr[idx][0] + di[e];
94 int rj = gArr[idx][1] + dj[e];
95
96 // find next golem close to current colem's exit
97 for (int d = 0; d < 4; d++) {
98 int ni = ri + di[d];
99 int nj = rj + dj[d];
100
101 if (ni < 0 || ni >= R || nj < 0 || nj >= C) continue;
102 if (m[ni][nj] == -1 || v[m[ni][nj]]) continue;
103
104 moveGolem(m[ni][nj]);
105 }
106 }
107
108 static void initMap() {
109 m = new int[R][];
110 for (int r = 0; r < R; r++) {
111 m[r] = new int[C];
112 Arrays.fill(m[r], -1);
113 }
114 }
115}
Comments