티스토리 뷰
#. Problem
* The copyright in this matter is in BOJ
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it
#. Solve
시뮬레이션 문제라서 사실 하라는 대로만 잘 구현하면 되는데
이 문제는 놓칠 수 있는 부분을 살짝 더 신경 써주어야 한다.
두 번이나 헤맸다는..
동작은 크게 5가지 과정의 반복이다.
1. 종두이노(종수의 아두이노)의 이동
2. 종두이노가 이상한 아두이노가 있는 칸으로 이동한 경우 게임 종료
3. 이상한 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워지는 방향으로 한 칸 이동
4. 이상한 아두이노가 종두이노가 있는 칸으로 이동한 경우에는 게임 종료
5. 같은 칸에 있는 이상한 아두이노는 모두 파괴
여기서 놓쳤던 부분은 (**신경 써주어야 하는 부분**)
* 아두이노는 동시에 이동한다는 점.
디버깅으로는 Queue에 있는 순서대로 아두이노들이 이동하지만 실제로는 동시에 이동한다.
여기서 같은 칸에 있는 이상한 아두이노를 모두 파괴하는 부분에서 어떻게 처리를 해주어야 할지 고민을 많이 했다.
아두이노마다 번호를 붙여 파괴된 아두이노의 상태를 관리해보기도 하고,
폭발이 일어날 좌표를 따로 저장했다가 마지막에 빈칸으로 만들어보기도 하고,
해당 좌표에 있는 아두이노의 개수를 관리하는 map 배열로 상태를 관리해보기도 하였다.
아두이노를 파괴하는 과정에서 문제가 있다고 생각하고 여러 처리 방법을 생각해보았는데...
결국 중요한 포인트는...! 바로 아래 설명할 map 배열 복사이다.
* map 배열 복사
자, (3, 3) 위치에서 폭발이 일어나 아두이노들이 파괴되어 빈칸이 되었다.
로직 상 다음 턴(종수의 다음 움직임)에서 Queue에서 꺼낸 좌표가 빈칸이라면,
해당 아두이노는 파괴된 것으로 간주하고 이동을 하지 않고 pass를 하게 된다.
// map[r][c]는 해당 좌표가 빈칸임을 의미
1 | if(map[now.r][now.c] == 0) continue; | cs |
하지만! 파괴된 아두이노가 Queue에서 꺼내지기 전에 다른 아두이노가 (3, 3)으로 이동하게 되면 map[3][3] = 1
파괴된 아두이노는 자신이 파괴되지 않은 것으로 착각하고 계속 이동해버리게 된다.
그래서 이전 턴에서의 map 상태를 관리해주어야 한다.
#. Code
map[2][R][C] 로 이전, 현재의 map 상태를 관리했다.
시작은 map[0][R][C]
map[0][1][2] = 3 은
(1, 2) 위치에 3개의 이상한 아두이노가 있다는 의미이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ8972 { static int R, C, IR, IC; static int[] dr = { 0, 1, 1, 1, 0, 0, 0, -1, -1, -1 }, dc = { 0, -1, 0, 1, -1, 0, 1, -1, 0, 1 }; static int map[][][]; static Queue<Robot> q; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); R = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken()); map = new int[2][R][C]; q = new LinkedList<>(); for (int r = 0; r < R; r++) { String input = br.readLine(); for (int c = 0; c < C; c++) { char now = input.charAt(c); // 종수의 위치 if (now == 'I') { IR = r; IC = c; } // 이상한 아두이노의 위치 else if (now == 'R') { map[0][r][c] = 1; q.add(new Robot(r, c)); } } } String command = br.readLine(); int res = process(command); // 중간에 게임이 끝나는 경우 if (res > 0) { System.out.println("kraj " + res); } else { res *= -1; map[res][IR][IC] = -1; for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { if(map[res][r][c] == 0) System.out.print('.'); else if(map[res][r][c] == -1) System.out.print('I'); else if(map[res][r][c] == 1) System.out.print('R'); } System.out.println(); } } } private static int process(String command) { int idx = 0; for (int i = 0; i < command.length(); i++) { // 이전 턴에서의 map 상태를 복사 copy(idx); // 1. 종두이노가 이동 int com = command.charAt(i) - '0'; IR += dr[com]; IC += dc[com]; // 2. 종두이노가 이상한 아두이노가 있는 칸으로 이동한 경우 게임 종료 if (map[idx][IR][IC] == 1) return i + 1; // 3. 이상한 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워지는 방향으로 한 칸 이동한다. int size = q.size(); Robot mLoc = new Robot(0, 0); while (size-- > 0) { Robot now = q.poll(); // 아두이노끼리 폭발이 일어난 자리라면 pass if(map[idx][now.r][now.c] == 0) continue; int mDist = Integer.MAX_VALUE; for (int d = 1; d <= 9; d++) { int rr = now.r + dr[d]; int cc = now.c + dc[d]; // 범위 if (rr < 0 || cc < 0 || rr >= R || cc >= C) continue; // |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동 int dist = Math.abs(IR - rr) + Math.abs(IC - cc); if (mDist > dist) { mDist = dist; mLoc = new Robot(rr, cc); } } // 이동할 좌표 q.add(mLoc); map[idx^1][mLoc.r][mLoc.c]++; map[idx^1][now.r][now.c]--; // 4. 이상한 아두이노가 종두이노가 있는 칸으로 이동한 경우에는 게임 종료 if (mLoc.r == IR && mLoc.c == IC) return i + 1; } // 5. 같은 칸에 있는 이상한 아두이노는 모두 파괴 for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { if(map[idx^1][r][c] > 1) map[idx^1][r][c] = 0; } } // 새로운 map을 Main map으로 전환 idx ^= 1; } return idx * -1; } private static void copy(int idx) { for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { map[idx^1][i][j] = map[idx][i][j]; } } } static class Robot { int r, c; public Robot(int r, int c) { this.r = r; this.c = c; } } } | cs |
line 67) 이전 map 상태를 새로운 map에 copy
line 84) 이 부분이 이전 map 상태를 관리해야하는 이유이다.
'현재 map'에서 확인하는 것이 아니라 '이전 map'에서 확인해주어야 한다.
line 100) 이상한 아두이노가 이동할 위치를 Queue에 추가
line 101 ~ 103) 이동할 위치에 아두이노의 개수를 + 1 해주고,
이동하기 전 위치의 아두이노 개수는 - 1
line 110 ~ 114) map[idx][r][c] 가 1보다 크다는 것은 해당 위치에 이상한 아두이노가 2개 이상 있다는 것이므로
폭발이 발생
line 119) return을 idx * -1 을 해준 이유는 최종으로 출력에 사용될 idx를 확인하기 위함이다.
-1 을 곱해준 이유는 중간에 게임이 끝나는 경우와 구별해주기 위해서였다.
'PS > Problem_Solving' 카테고리의 다른 글
[BOJ] 6593. 상범 빌딩(BFS).java (0) | 2020.11.19 |
---|---|
[BOJ] 1759. 암호 만들기(조합).java (0) | 2020.11.19 |
[BOJ] 14465. 소가 길을 건너간 이유 5(누적합).java (0) | 2020.11.15 |
[BOJ] 15886. 내 선물을 받아줘 2(DFS).java (0) | 2020.11.15 |
[BOJ] 2841. 외계인의 기타 연주(Stack).java (0) | 2020.11.15 |