[백준 3197] 백조의 호수

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

호수는 행이 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'은 백조가 있는 공간으로 나타낸다.

출력

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

---

예제 입력 3

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

예제 출력 3

2

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static boolean[][] visited;
    public static boolean[][] iceVisited;
    public static char[][] arr;
    public static int R, C;
    public static int[] dr = {-1, 1, 0, 0};
    public static int[] dc = {0, 0, 1, -1};
    public static Deque<Point> nextDq, queue, moveQueue;

    public static class Point {
        int r;
        int c;

        public void setR(int r) {
            this.r = r;
        }
        public void setC(int c) {
            this.c = c;
        }

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];
        nextDq = new ArrayDeque<>();    // 얼음이 녹을 곳 저장
        queue = new ArrayDeque<>();     // 시작위치
        moveQueue = new ArrayDeque<>();
        for(int i = 0; i < R; i++) {
            String str = br.readLine();
            for(int j = 0; j < C; j++) {
                arr[i][j] = str.charAt(j);
                if (arr[i][j] == 'L') {
                    arr[i][j] = '.';
                    queue.add(new Point(i, j));
                }
            }
        }
        iceVisited = new boolean[R][C];
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(arr[i][j] == '.') {
                    for(int d = 0; d < 4; d++) {
                        int nr = i + dr[d];
                        int nc = j + dc[d];
                        if(nr >= 0 && nr < R && nc >= 0 && nc < C && arr[nr][nc] == 'X' && !iceVisited[nr][nc]) {
                            iceVisited[nr][nc] = true;
                            arr[nr][nc] = 'x';
                            nextDq.add(new Point(nr, nc));
                        }
                    }
                }
            }
        }
        
        int cnt = 0;
        Point to = queue.pollLast();
        visited = new boolean[R][C];
        
        Loop1:
        while(true) {
            cnt++;
            int k = nextDq.size();
            for(int i = 0; i < k; i++) { // 다음에 녹을 빙판 큐에 넣어둠
                Point current = nextDq.poll();
                arr[current.r][current.c] = '.';
                for(int d = 0; d < 4; d++) {
                    int nr = current.r + dr[d];
                    int nc = current.c + dc[d];
                    if(nr >= 0 && nr < R && nc >= 0 && nc < C && !iceVisited[nr][nc] && arr[nr][nc] == 'X') {
                        nextDq.add(new Point(nr, nc));
                        iceVisited[nr][nc] = true;
                        arr[nr][nc] = 'x';
                    }
                }
            }

            while(!queue.isEmpty()) {
                Point current = queue.poll();
                if(current.r == to.r && current.c == to.c) {
                    break Loop1;
                }
                visited[current.r][current.c] = true;
                for(int d = 0; d < 4; d++) {
                    int nr = current.r + dr[d];
                    int nc = current.c + dc[d];
                    if(nr >= 0 && nr < R && nc >= 0 && nc < C && arr[nr][nc] != 'X' && !visited[nr][nc]) {
                        if(arr[nr][nc] == 'x') {
                            moveQueue.add(new Point(nr, nc));
                        } else {
                            queue.add(new Point(nr, nc));
                        }
                        visited[nr][nc] = true;
                    }
                }
            }
            while(!moveQueue.isEmpty()) {
                queue.add(moveQueue.poll());
            }
            moveQueue.clear();
        }

        bw.write(Integer.toString(cnt));
        br.close();
        bw.flush();
        bw.close();
    }
}

 

 

시간제한이 1초고 R과 C가 1~1500이기 때문에 단순 bfs로는 시간초과가 나게 된다.

 

얼음이 녹을 수 있는 위치만 저장하여 큐에 넣고 해당 얼음이 녹으면 물이 되니 그 다음에 녹을 위치를 소문자x로 저장해둔다. 모든 얼음을 큐에 넣고 돌리는것에서 변화하는 얼음만 담으면 시간초과가 나지 않게 된다.

 

입력 시 백조의 위치를 찾으면 해당 부분을 백조의 위치가 담긴 큐에 넣고 해당값을 물로 바꾼다.

 

입력받을 때부터 백조는 빙판으로부터 갈라져 있어 만나지 못하기 때문에 바로 다음에 얼음이 녹을 빙판을 찾는다.

 

빙판을 찾을 때는 물일 경우 해당 물 사방에 빙판이 있는지 dr, dc배열을 이용해 찾고 경계면을 벗어나지 않고 인접한 부분이 있고 빙판일 경우 재방문하지 않기 위해 iceVisited을 이용해 관리하고 'x'로 변경한다.

 

백조는 하나만 이동하면 되기 때문에 마지막에 저장했던 위치나 처음에 저장했던 위치 둘 중 아무거나 고르면 된다.

 

bfs를 도는데 여기서 주의할 점이 while(!nextDq.isEmpty())를 사용하게 되면 큐의 내용이 다 없어질 수 있기 때문에 녹을 빙판만큼만 돌기 위한 size()를 이용해 for문으로 순회한다.

 

빙판을 녹이고 다음 빙판이 녹을 부분을'X'로 지나가지 않기 위해 'x'로 치환하고 한번 녹았을 때 백조들을bfs를 돈다.

 

그리고 백조가 bfs를 돌아 'x'인 부분 옆(다음에 녹을 빙판 전)에 있을 경우에 다음에 움직일 moveQueue에 담는다.

 

queue의 순회가 끝나면 queue는 비어있는 상태이고 moveQueue는 다음에 이동할 백조의 위치를 갖고 있기 때문에 moveQueue의 값을 전부 queue에 넣는다.