티스토리 뷰

반응형


#. 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] == 0continue;
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 = { 0111000-1-1-1 }, dc = { 0-101-101-101 };
    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] == 0System.out.print('.');
                    else if(map[res][r][c] == -1System.out.print('I');
                    else if(map[res][r][c] == 1System.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] == 1return i + 1;
 
            // 3. 이상한 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워지는 방향으로 한 칸 이동한다.  
            int size = q.size();
            Robot mLoc = new Robot(00);
            while (size-- > 0) {
                
                Robot now = q.poll();
                // 아두이노끼리 폭발이 일어난 자리라면 pass
                if(map[idx][now.r][now.c] == 0continue;
                
                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 을 곱해준 이유는 중간에 게임이 끝나는 경우와 구별해주기 위해서였다.

반응형
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday