[백준]3197 백조의 호수

3197번: 백조의 호수 (acmicpc.net)

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

 

내 풀이

우선 입력의 범위를 보면 기존의 비슷한 유형의 문제를 풀때 풀이를 적용하면 안될 것 같았다.

마땅한 풀이가 생각나지 않는 상황에서 혹시나 싶어서 시도는 해봤다 ㅎㅎ...

매 날짜마다 얼음이 녹는 것을 반영하면서 매일 백조가 만날 수 있는지 BFS탐색을 하는 것이다

 

너무나 당연하게도 통과가 안된다...

예전에는 이런 문제를 몇시간씩 붙잡고 고민했었지만, 최근 나의 생각은 인풋이 있어야 아웃풋도 있는 법, 천재가 아니기에 최적화된 풀이를 따라갈 풀이를 내가 즉석으로 만들어낼 수 없다는 것을 인정하고 좋은 풀이를 머리에 넣기 위해 빠른 검색을 하였다.

 

[BOJ 3197] 백조의 호수 (Java) (velog.io)

[BOJ 3197] 백조의 호수 (Java)

 

위의 글의 풀이 과정을 보고 구현을 하는 방법으로 해결함

핵심 내용은 매번 탐색을 다시 다 하는 것이 아니라 이전에 수행했던 내용을 반영해서 탐색을 하는 것

즉 오리가 다른 오리를 찾기위해 탐색을 하고 못찾으면 다시 처음부터 탐색을 하는 것이 아닌 이전에 탐색을 했던 부분을 건너띄고 탐색을 하게 하여 최적화를 하는 것

 

이 문제에선 물과 인접한 빙판이 매일 녹고 오리는 물에서만 이동하니 내일, 다음 턴에 이동을 시작하는 장소를 물과 인접한 빙판이라는 것이 포인트

 

이를 어떻게 하였냐면

waterQueue - 물이 될 좌표를 넣는 큐

findQueue - 오리가 탐색을 시작할 좌표를 넣는 큐

NextQueue - 다음 날짜에 오리가 탐색을 시작할 좌표를 잠시 담는 버퍼가 되어줄 큐 

를 생성하여 이를 이용하여 위의 내용을 구현

 

처음 데이터 입력 받을 때 

오리가 있는 좌표까지 물로 취급하여 물은 waterQueue에 넣고

첫번째 오리의 좌표를 findQueue에 넣습니다

 

public static void sol() {
        findQueue.add(new Coord(targetRow1, targetCol1));
        checked[targetRow1][targetCol1] = true;
        int day = 0;
        while (!find()) {
            melt();
            day++;
        }
        System.out.println(day);    
}

sol()에서

find(), 즉 첫번째 오리 기준으로 두번째 오리를 찾을 수 있을까지 반복하고

못 찾는다면 melt()를 돌린다

melt()는 녹을 물을 녹이고 녹은 지점을 waterQueue에 넣는 과정을 한다

그리고 날짜를 +1 해줌으로 시간의 흐름을 표현한다.

public static void melt(){

        // 녹을 물 녹이고 녹은 지점들 다시 waterQueue에 넣어야함
        Queue<Coord> queue = new LinkedList<>();

        while (!waterQueue.isEmpty()) {
            Coord cur = waterQueue.poll();            
            for (int k = 0; k < 4; k++) {

                int nextRow = cur.row + moveSet[k][0];
                int nextCol = cur.col + moveSet[k][1];

                if (nextRow <= 0 || nextCol <= 0 || nextRow > R || nextCol > C) {
                    continue;
                }

                //빙판이면
                if (!map[nextRow][nextCol]) {
                    map[nextRow][nextCol] = true;                    
                    queue.add(new Coord(nextRow, nextCol));
                }
            }
        }

        while (!queue.isEmpty()) {
            waterQueue.add(queue.poll());
        }
    }

melt() 에선 

waterQueue에 담긴 현재 물인 좌표들을 활용하여 물과 인접한 빙판 좌표를 waterQueue에 새롭게 넣는다.

 

public static boolean find() {

        while(!findQueue.isEmpty()){
            Coord cur = findQueue.poll();          
            if (cur.row == targetRow2 && cur.col == targetCol2) {
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nextRow = cur.row + moveSet[i][0];
                int nextCol = cur.col + moveSet[i][1];

                if (nextRow <= 0 || nextCol <= 0 || nextRow > R || nextCol > C) {
                    continue;
                }

                if (checked[nextRow][nextCol]) {
                    continue;
                }

                checked[nextRow][nextCol] = true;
                //빙판이면 nextQueue에 넣기
                if (!map[nextRow][nextCol]) {
                    nextQueue.add(new Coord(nextRow, nextCol));                  
                }else{
                    findQueue.add(new Coord(nextRow, nextCol));
                }
            }
        }
        
        while (!nextQueue.isEmpty()) {
            findQueue.add(nextQueue.poll());
        }
        return false;
    }

find()에서  오리가 물만을 밟으며 이동하는데 빙판을 만나면

내일은 이곳에서 탐색을 시작할 것이니깐 nextQueue에 넣고  

오늘의 탐색이 끝나고 (findQueue가 빌 때까지 탐색) nextQueue의 내용을 findQueue로 옮기면서 내일의 탐색을 준비

 

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader input;
    static StringBuilder output = new StringBuilder();
    static String src = "8 17\n" +
            "...XXXXXX..XX.XXX\n" +
            "....XXXXXXXXX.XXX\n" +
            "...XXXXXXXXXXXX..\n" +
            "..XXXXX.LXXXXXX..\n" +
            ".XXXXXX..XXXXXX..\n" +
            "XXXXXXX...XXXX...\n" +
            "..XXXXX...XXX....\n" +
            "....XXXXX.XXXL...";

    static int R, C, targetRow1, targetCol1, targetRow2, targetCol2;
    static boolean[][] map, checked;
    static Queue<Coord> waterQueue = new LinkedList<>();
    static Queue<Coord> nextQueue = new LinkedList<>();
    static Queue<Coord> findQueue = new LinkedList<>();
    static int[][] moveSet = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));

        StringTokenizer str = new StringTokenizer(input.readLine());
        R = Integer.parseInt(str.nextToken());
        C = Integer.parseInt(str.nextToken());

        // .: 물 X: 빙판, L: 백조
        // 날마다 물과 인접한 빙판 녹음

        map = new boolean[R + 1][C + 1];
        checked = new boolean[R + 1][C + 1];

        boolean isFirst = true;
        for (int i = 0; i < R; i++) {
            String line = input.readLine();
            for (int j = 0; j < C; j++) {
                if (line.charAt(j) == '.') {
                    waterQueue.add(new Coord(i + 1, j + 1));
                    map[i + 1][j + 1] = true;
                } else if (line.charAt(j) == 'L') {
                    map[i + 1][j + 1] = true;
                    waterQueue.add(new Coord(i + 1, j + 1));
                    if(isFirst){
                        targetRow1 = i + 1;
                        targetCol1 = j + 1;
                        isFirst = false;
                    }else{
                        targetRow2 = i + 1;
                        targetCol2 = j + 1;
                    }
                }
            }
        }
        sol();
    }

    public static void sol() {
        findQueue.add(new Coord(targetRow1, targetCol1));
        checked[targetRow1][targetCol1] = true;
        int day = 0;
        while (!find()) {            
            melt();
            day++;
        }
        System.out.println(day);
    }

    public static boolean find() {

        while(!findQueue.isEmpty()){
            Coord cur = findQueue.poll();          
            if (cur.row == targetRow2 && cur.col == targetCol2) {
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nextRow = cur.row + moveSet[i][0];
                int nextCol = cur.col + moveSet[i][1];

                if (nextRow <= 0 || nextCol <= 0 || nextRow > R || nextCol > C) {
                    continue;
                }

                if (checked[nextRow][nextCol]) {
                    continue;
                }

                checked[nextRow][nextCol] = true;
                //빙판이면 nextQueue에 넣기
                if (!map[nextRow][nextCol]) {
                    nextQueue.add(new Coord(nextRow, nextCol));                  
                }else{
                    findQueue.add(new Coord(nextRow, nextCol));
                }
            }
        }
        
        while (!nextQueue.isEmpty()) {
            findQueue.add(nextQueue.poll());
        }
        return false;
    }


    public static void melt(){

        // 녹을 물 녹이고 녹은 지점들 다시 waterQueue에 넣어야함
        Queue<Coord> queue = new LinkedList<>();

        while (!waterQueue.isEmpty()) {
            Coord cur = waterQueue.poll();            
            for (int k = 0; k < 4; k++) {

                int nextRow = cur.row + moveSet[k][0];
                int nextCol = cur.col + moveSet[k][1];

                if (nextRow <= 0 || nextCol <= 0 || nextRow > R || nextCol > C) {
                    continue;
                }

                //빙판이면
                if (!map[nextRow][nextCol]) {
                    map[nextRow][nextCol] = true;                    
                    queue.add(new Coord(nextRow, nextCol));
                }
            }
        }

        while (!queue.isEmpty()) {
            waterQueue.add(queue.poll());
        }
    }
    public static class Coord{
        int row;
        int col;

        public Coord(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}