[백준] Silver 1. 봄버맨

https://www.acmicpc.net/problem/16918

 

사용 알고리즘

• BFS
• 구현

풀이

    static int r, n, c;
    static char [][] board;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Queue<int[]> queue = new LinkedList<>();

    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());
        n = Integer.parseInt(st.nextToken());

        board = new char[r][c];
        for(int i = 0; i < r; i++) {
            String input = br.readLine();
            for(int j = 0; j < c; j++) {
                board[i][j] = input.charAt(j);
            }
        }

        for(int t = 2; t <= n; t++) {
            if (t % 2 == 0) { // 폭탄 위치를 저장함
                for(int i = 0; i < r; i++){
                    for(int j = 0; j < c; j++) {
                        if (board[i][j] == 'O')
                            queue.add(new int[]{i, j});
                        board[i][j] = 'O';
                    }
                }
            }

            else if (t % 2 != 0) {
                bfs();
            }
        }
        print();
    }

    public static void bfs() {
        while(!queue.isEmpty()) {
            int [] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            board[x][y] = '.';
            for(int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                if (board[nx][ny] == 'O')
                    board[nx][ny] = '.';
            }
        }
    }

    public static void print() {
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }
}

 

회고

 

계속 안풀려서 정신 나갈뻔했다. 구현 문제일수록 침착하게 조건을 생각하고 풀이를 하는게 중요할 것 같다.

 

일단, 문제에서 시간에 따른 상태 변화를 살펴보자.

0초: 초기 입력값
1초: 아무것도 하지 않음
2초: 폭탄 설치
3초: 초기에 설치해둔 폭탄 터짐
4초 : 폭탄 설치
5초: 2초에 설치해둔 폭탄 터짐
6초: 폭탄 설치
7초: 4초에 설치해둔 폭탄 터짐

 

패턴을 보면 설치, 터짐 과정이 반복된다고 보면 될 것같다. 0초, 1초는 입력받은 값 그 자체이므로 2초일 때 부터 n까지 루프를 돌리면서 체크하면 된다.

for(int t = 2; t <= n; t++) {
	...
}

 

그리고, t가 2로 나누어 떨어질 때는 폭탄 설치를 해야 하므로, 모든 좌표를 폭탄으로 바꿔 주어야 한다.

 

그리고, 제일 중요한 것이 기존에 있던 폭탄의 좌표를 큐에 담는 것이다. 이렇게 담아 주어야, 폭탄을 터뜨릴 때 큐에 담긴 좌표를 보고서 배열을 업데이트 할 수 있다.

if (t % 2 == 0) { // 폭탄 위치를 저장함
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++) {
            if (board[i][j] == 'O')
                queue.add(new int[]{i, j});
            board[i][j] = 'O';
        }
    }
}

 

t가 2로 나누어 떨어지지 않을 때는, 폭탄을 터뜨리면 된다. 큐에 저장되어 있는 해당 좌표들을 순회하면서

• 본인 좌표 포함 상하좌우를 '.'(빈칸)으로 변환해준다.

그리고, 맨 마지막에 결과값을 출력해주면 되는 문제였다.

 

문제를 풀면서 가장 헷갈렸던 부분은, 어느 시점에서 큐에 좌표를 저장해주는가 였다.

 

폭탄을 터뜨리려면, 큐에 좌표가 저장되어 있어야 했는데 이 과정을 폭탄 설치를 할 때 같이 할 생각을 못했다. 

 

그리고, 배열 값을 '.'으로 변환해줄 때, 무지성으로 큐에 {nx,ny} 좌표들을 넣어주었다... 폭탄 설치를 할 때 좌표들을 다 넣어주는데 불필요한 작업이다.