[백준] 3197번 - 백조의 호수 (Java)

문제를 읽어봤을 때 대충 풀어봤던 백준 문제 중에 '치즈' 라는 문제와 비슷해보여서 쉬울 줄 알았다.

백조가 만나야한다는 요소만 추가된 문제인줄 알았다.

그렇지만 플레5인 이유가 있었다..! '치즈'에서 풀었던 방식으로 똑같이 풀으려했더니 시간초과가 났다.

그래서 다른사람들의 풀이를 참고하여서 다시 풀어보았다.

 

 

<문제>

https://www.acmicpc.net/problem/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'은 백조가 있는 공간으로 나타낸다.

 

출력

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

 

 

 

 

<풀이>

일단, 로직은 다음과 같다.

1) 두 백조가 만날 수 있는지 BFS로 확인 -> 만났다면 종료

2) 물에 닿은 얼음이 녹는것을 BFS로 구현

 

이러한 로직으로 만날때까지 반복하여 며칠이 걸리는지 구하는 것이다.

그런데, 일반적인 BFS로 구현한다면, 시간초과가 날 수밖에 없다.

왜나면 최악의 경우 r과 c가 1500이므로 1500 * 1500 * 1499(얼음이 다 녹는 최악의 일수) 이므로 너무 큰 숫자이다.

 

그래서 BFS를 돌때 처음부터 도는 것이 아니라 이전에 막혔던? 부분을 저장해서 그곳부터 시작해야한다.

위 로직으로 본다면,

1) 두 백조가 만나지 못했을 경우 -> 큐에 'X'를 만났을 지점을 넣어서 다음에 그곳부터 BFS 시작

2) 큐에 얼음이 녹은 지점을 넣어서 다음에 그곳부터 BFS 시작

 

이런식으로 한다면 시간초과를 면하고 답을 구할 수 있다.

또 다른분들 풀이를 보니, 이분탐색으로 일수를 구하는 방법도 있다고 한다.

 

 

**주의해야할점**

풀면서 계속 58%?에서 틀려서 뭐지 싶었는데, 그 이유를 알고나서 매우 화가났다..!

알고보니 백조가 있는 곳도 물위라서 물으로 취급해야한다.

그래서 백조와 닿아있는 얼음도 녹아야한다.

백조가 있는 곳도 물이라고 한번더 문제에서 강조해줬으면 좋겠는데,,, ㅠㅠㅠㅠㅠ

이것때메 좀 헤맸다. 다른분들은 헤매지 않길...ㅠㅠㅠㅠㅠ

 

 

그래도 BFS에서 조금 더 응용한 문제같아서 좋은 문제 같았다.

이렇게 이전의 결과를 큐에 저장했다가 그곳부터 다시 BFS를 하는 것은 생각치 못했는데,

하나 더 배웠으니 풀길 잘했다고 생각이 드는 문제다.

 

 

<코드>

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

class Main {
    static int r,c;
    static char[][] map;
    static int[] dx = {0,1,0,-1}, dy = {1,0,-1,0};
    static int[][] swans = new int[2][2];
    static Queue<int[]> meltQueue = new LinkedList<>();
    static Queue<int[]> swanQueue = new LinkedList<>();

    public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int answer = 0;

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        map = new char[r][c];
        boolean[][] swanVisited = new boolean[r][c];

        int idx = 0;

        for (int i = 0; i < r; i++) {
            String str = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j] == 'L') {
                    swans[idx][0] = i;
                    swans[idx++][1] = j;
                }
                if(map[i][j] != '.') {
                    meltQueue.add(new int[]{i,j});
                }
            }
        }
        swanQueue.add(new int[]{swans[0][0], swans[0][1]});
        swanVisited[swans[0][0]][swans[0][1]] = true;

        while(!swansCanMeet(swanVisited)) {
            melt();
            answer++;
        }

        br.close();
		System.out.print(answer);
	}

    private static boolean swansCanMeet(boolean[][] swanVisited) {
        Queue<int[]> nextQueue = new LinkedList<>();

        while(!swanQueue.isEmpty()) {
            int x = swanQueue.peek()[0];
            int y = swanQueue.peek()[1];
            swanQueue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx<0 || nx>=r || ny<0 || ny>=c || swanVisited[nx][ny]) continue;
                swanVisited[nx][ny] = true;
                if(nx == swans[1][0] && ny == swans[1][1]) {
                    return true;
                } else if(map[nx][ny] == 'X') {
                    nextQueue.add(new int[]{nx,ny});
                } else {
                    swanQueue.add(new int[]{nx, ny});
                }
            }
        }
        swanQueue = nextQueue;
        return false;
    }

    private static void melt() {
        int size = meltQueue.size();

        for(int i=0; i<size; i++) {
            int x = meltQueue.peek()[0];
            int y = meltQueue.peek()[1];
            meltQueue.poll();

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
                if(map[nx][ny] == 'X') { //물에 닿아있는 얼음 -> 녹아야함
                    map[nx][ny] = '.';
                    meltQueue.add(new int[]{nx,ny});
                }
            }
        }
    }
}