[백준] 3197번 : 백조의 호수

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

 

# 출력

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

 

# 예제 입력

8 17

...XXXXXX..XX.XXX

....XXXXXXXXX.XXX

...XXXXXXXXXXXX..

..XXXXX.LXXXXXX..

.XXXXXX..XXXXXX..

XXXXXXX...XXXX...

..XXXXX...XXX....

....XXXXX.XXXL...

 

# 예제 출력

2

---

[너비 우선 탐색(Breadth-First Search, BFS)]

하루를 허비하게 해준 문제이다. 이 문제는 2개의 BFS를 이용해야한다. 따라서 Queue도 2개가 필요하다. 얼음을 녹이는 waterBFS와 백조가 다른 백조를 찾아가는 swanBFS를 사용했다. 두 함수는 Queue를 이용하고 다른 정점을 다시 Queue에 넣는다는 점에서 동일한 BFS이지만, 서로 기능은 완전히 다르다.

 

# swanBFS()

백조를 시작으로 주변 갈 수 있는 곳을 모두 탐험한다.

> 물(.)이면 다시 Queue에 넣고 얼음 또는 다른 백조를 만날 때 까지 탐헌한다.

> 얼음(X)이면 물(.)로 변경하고 tempQueue에 잠시 넣어둔다. (하루가 지나고 다시 쓰여져야 하기 때문)

> 다른 백조(L)면 프로그램의 종료 Flag를 true로 변경하고 반복문을 종료한다.

    static void swanBFS(){
        Queue<Point> tmpQ = new LinkedList<>();

        while(!swanQ.isEmpty()){
            Point p = swanQ.poll();

            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = p.y+Y[a];
                int nx = p.x+X[a];
                if(ny <= 0 || nx <= 0 || ny > r || nx > c || visit[ny][nx]) continue;

                if(map[ny][nx] == '.')
                    swanQ.add(new Point(ny, nx));
                else if(map[ny][nx] == 'L'){
                    find = true;
                    return;
                }
                else if(map[ny][nx] == 'X') {
                    map[ny][nx] = '.';
                    tmpQ.add(new Point(ny, nx));
                }

                visit[ny][nx] = true;
            }
        }
        swanQ = tmpQ;
    }

 

# waterBFS()

상하좌우 정점을 둘러보고 얼음(X)이면 물(.)로 변경한다. 다시 큐에 넣는다.

    static void waterBFS(){
        //얼음 녹이기
        int tmp = waterQ.size();

        for(int i=0; i<tmp; i++){
            Point p = waterQ.poll();

            for(int a=0; a<4; a++){
                int ny = p.y+Y[a];
                int nx = p.x+X[a];

                if(ny <= 0 || nx <= 0 || ny > r || nx > c) continue;

                if(map[ny][nx] == 'X') {
                    map[ny][nx] = '.';
                    waterQ.add(new Point(ny, nx));
                }
            }
        }
    }

# Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){ y=yy; x=xx; }
    }
    static Queue<Point> waterQ = new LinkedList<>(), swanQ = new LinkedList<>();
    static int r, c, day = 0;

    static boolean[][] visit;
    static char[][] map;

    static Point[] swan = new Point[2];
    static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
    static boolean find;

    static void waterBFS(){
        //얼음 녹이기
        int tmp = waterQ.size();

        for(int i=0; i<tmp; i++){
            Point p = waterQ.poll();

            for(int a=0; a<4; a++){
                int ny = p.y+Y[a];
                int nx = p.x+X[a];

                if(ny <= 0 || nx <= 0 || ny > r || nx > c) continue;

                if(map[ny][nx] == 'X') {
                    map[ny][nx] = '.';
                    waterQ.add(new Point(ny, nx));
                }
            }
        }
    }

    static void swanBFS(){
        Queue<Point> tmpQ = new LinkedList<>();

        while(!swanQ.isEmpty()){
            Point p = swanQ.poll();

            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = p.y+Y[a];
                int nx = p.x+X[a];
                if(ny <= 0 || nx <= 0 || ny > r || nx > c || visit[ny][nx]) continue;

                if(map[ny][nx] == '.')
                    swanQ.add(new Point(ny, nx));
                else if(map[ny][nx] == 'L'){
                    find = true;
                    return;
                }
                else if(map[ny][nx] == 'X') {
                    map[ny][nx] = '.';
                    tmpQ.add(new Point(ny, nx));
                }

                visit[ny][nx] = true;
            }
        }
        swanQ = tmpQ;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = 1501, a = 0;

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        visit = new boolean[N][N];
        map = new char[N][N];

        for(int i=1; i<=r; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=c; j++) {
                map[i][j] = str[j - 1];

                if(map[i][j] == 'L')
                    swan[a++] = new Point(i, j);

                if(map[i][j] != 'X')
                    waterQ.add(new Point(i, j));
            }
        }

        visit[swan[0].y][swan[0].x] = true;
        swanQ.add(new Point(swan[0].y, swan[0].x));

        while(!find) {
            swanBFS();

            if(find) break;

            waterBFS();
            day++;
        }
        System.out.println(day);
    }
}