백준 3179번: 백조의 호수 (JAVA)

https://www.acmicpc.net/workbook/view/7313

문제집: 0x09강 - BFS (BaaaaaaaaaaarkingDog)

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

 

---

 

문제 풀다보면 실력이 늘긴 하나보다. 예전에는 감도 안 잡혀서 '나중에 봐야지'하고 했는데, 오늘 다시보니까 30분도 안 걸려서 푼 듯하다. 다만 언제나 그렇듯이, 조건 체크 실수해서 한 번 틀린게 아쉽다.

 

풀이

cf) 안 되는 풀이

매 시간마다 bfs를 쌩으로 돌려버리면 방문처리하는 이차원 boolean 배열만 최대 1500/2번 근처로 만들어야 하는데, 이는 최대 1500*1500*(1500/2)번의 단위 연산을 요구한다 -> 당연히 TLE다.

 

그래서, 매 시행마다 '다음에 새로운 위치로 갈 수 있는 백조의 후보군'을 따로 저장할 필요가 있다.

풀이의 편의를 위해, 백조를 '1'과 '2'로 나누었다. 총 5개의 queue를 사용했다.

1) 백조 1에 대해 bfs를 진행할 queue 'swan1'

2) 녹을 얼음과 맞닿아아있는 백조들을 모은 queue 'nextSwan1'

3) 백조 2에 대해 bfs를 진행할 queue 'swan2'

4) 녹을 얼음과 맞닿아아있는 백조들을 모은 queue 'nextSwan2'

5) 오늘 녹을 얼음들을 저장하는 queue 'edge'

 

'예제 입력 2'를 통해 그림으로 설명해보도록 한다.

처음 상태(day = 0)는 다음과 같다.

 

 

두 백조를 각각 1, 2로 나타내준다.

 

 

X가 아닌 다른 값(백조도 포함이다: 이 부분을 틀림!)과 맞닿은 얼음은 다음 날에 녹는다: 녹을 얼음을 edge에 넣어준다.

 

 

백조 1, 2에 대해 일반적으로 bfs를 진행하면 다음과 같이 된다.

 

 

이 중, 초록색과 보라색으로 마킹한 부분이 각각 다음 날 얼음이 녹아서 새로운 위치로 갈 수 있는 백조 위치의 후보군이다. 초록색 위치를 nextSwan1, 보라색 위치를 nextSwan2에 넣어주고, 다음날에는 해당 queue로 bfs를 진행하면 된다.

 

 

 

얼음은 딱 1단계만 녹아야한다: bfs를 1단계만 실행해준 후, 도달한 원소는 새로운 경계가 되니 edge에 넣어준다. 이 과정이 딱 1일이다. 백조 1과 2가 갈 수 있는 영역을 bfs로 방문해주고(그림에는 이 과정까지 진행됐다.), 이를 한 번 더 반복하면,

 

 

이렇게 된다. 그 다음 날에는 백조 1과 백조 2가 만날 수 있으니, 총 2일이 걸리게 된다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	
    static int R, C;
    static char[][] map;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    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 char[R][C];
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);
            }
        }
		
        // 다음 깨질 얼음은 방문처리해야 효율적인 코드가 된다.
        boolean[][] visited = new boolean[R][C];
        Queue<int[]> swan1 = new ArrayDeque<>();
        Queue<int[]> swan2 = new ArrayDeque<>();
        Queue<int[]> edge = new ArrayDeque<>();
        // 백조 1, 2 구분을 위한 코드
        boolean firstSwan = true;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'L') {
                    if (firstSwan) {
                        firstSwan = false;
                        map[i][j] = '1';
                        swan1.add(new int[] {i, j});
                    }
                    else {
                        map[i][j] = '2';
                        swan2.add(new int[] {i, j});
                    }
                }
                // 녹을 얼음을 경계 큐에 저장
                if (isEdge(i, j)) {
                    edge.add(new int[] {i, j});
                }
            }
        }

        int ans = 0;
        while (!swan1.isEmpty() || !swan2.isEmpty() || !edge.isEmpty()) {
            Queue<int[]> nextSwan1 = new ArrayDeque<>();
            // 백조 1 bfs
            while (!swan1.isEmpty()) {
                int[] cur = swan1.poll();
                int r = cur[0], c = cur[1];
                // 근처에 얼음이 있을 경우: 다음 날에 새로운 곳으로 갈 수 있는 위치의 후보군
                if (isNearIce(r, c)) nextSwan1.add(cur);
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                    // 백조 1이 백조 2를 만난 경우
                    // WLOG 백조 2가 백조 1을 만나는 경우는 안 짜도 된다.
                    if (map[nr][nc] == '2') {
                        System.out.println(ans);
                        return;
                    }
                    // 물이라면 이동하기: 방문처리를 숫자를 바꿔서 구현
                    if (map[nr][nc] == '.') {
                        map[nr][nc] = '1';
                        swan1.offer(new int[] {nr, nc});
                    }
                }
            }
            swan1 = nextSwan1;
		
            // 백조 2 bfs
            Queue<int[]> nextSwan2 = new ArrayDeque<>();
            while (!swan2.isEmpty()) {
                int[] cur = swan2.poll();
                int r = cur[0], c = cur[1];
                if (isNearIce(r, c)) nextSwan2.add(cur);
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                    if (map[nr][nc] == '.') {
                        map[nr][nc] = '2';
                        swan2.offer(new int[] {nr, nc});
                    }
                }
            }
            swan2 = nextSwan2;

            int size = edge.size();
            // 하루에 한 단계만 bfs 돌기
            while (size-- > 0) {
                int[] cur = edge.poll();
                int r = cur[0], c = cur[1];
                map[r][c] = '.';
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                    if (visited[nr][nc]) continue;
                    if (map[nr][nc] == 'X') {
                        visited[nr][nc] = true;
                        edge.offer(new int[] {nr, nc});
                    }
                }
            }
            ans++;
        }
    }

    // 경계에 있어서 녹을 얼음인지 확인하는 method
    static boolean isEdge(int x, int y) {
        if (map[x][y] != 'X') return false;
        for (int i = 0; i < 4; i++) {
            int nx = x + dr[i], ny = y + dc[i];
            if (nx >= 0 && nx < R && ny >= 0 && ny < C && map[nx][ny] != 'X') {
                return true;
            }
        }
        return false;
    }

    // 근처에 얼음이 있는지 확인하는 method
    static boolean isNearIce(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dr[i], ny = y + dc[i];
            if (nx >= 0 && nx < R && ny >= 0 && ny < C && map[nx][ny] == 'X') {
                return true;
            }
        }
        return false;
    }
}