[백준] 3197 백조의 호수 (JAVA)

문제 링크:

3197번: 백조의 호수

 

 

난이도: 플래티넘 5

 

 

문제:

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

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

 

 

출력:

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

 

 

문제이해:

문제를 이해하는 것은 어렵지 않다.

 

주어진 행렬에는 물(.), 빙판(X), 그리고 두 마리의 백조(L)가 존재한다.
매일 시간이 흐를 때마다 모든 물 칸은 상·하·좌·우 인접한 빙판을 녹여 물로 바꾼다.
이 과정을 반복하면서, 두 백조가 빙판에 막히지 않고 물길을 따라 서로 만날 수 있게 되는 최소 일수를 구하는 문제이다.

 

 

구현 방향:

작성자는 처음에 빙판을 물로 녹이는 BFS와, 한 마리 백조의 위치에서 시작해 다른 백조까지 도달하는 BFS를 각각 구현하였다. 즉, 두 개의 BFS를 동시에 사용하여 문제를 해결하려 했지만, 이 방식은 매일 전체 격자를 다시 탐색해야 하므로 시간복잡도가 O((R×C)²)에 이르러 결국 시간 초과가 발생하였다.

 

이 과정에서 “플래티넘 5 문제는 역시 쉽지 않다”는 점을 실감하게 되었다.

 

그러나 블로그를 통해 효율적인 구현 방향을 확인할 수 있었다. 핵심은 물 전체를 매일 검사하는 것이 아니라, 빙판 중 물과 접촉하여 실제로 녹을 수 있는 경계만 큐에 넣고 처리하는 방식이다. 녹지 못한 빙판은 water 큐에 저장해 두었다가 다음 날에만 확인하므로, 각 칸은 최대 한 번만 녹게 된다. 따라서 물 확장 과정의 시간복잡도는 O(R×C) 으로 단축된다.

 

백조 탐색도 마찬가지다. 당장 만날 수 없다면, 탐색 도중 부딪힌 빙판 좌표만 큐에 저장해 두었다가 다음 날 물로 변했을 때 이어서 탐색한다. 이미 탐색을 마친 영역은 다시 확인하지 않으므로, 매일 처음부터 BFS를 반복할 필요가 없다. 결과적으로 백조 탐색 또한 O(R×C) 로 처리할 수 있으며, 전체 알고리즘의 시간복잡도는 O(R×C) 로 줄어든다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

 

실패코드(시간초과):

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

public class Main {
    static int R, C;
    static char[][] matrix;
    static boolean[][] visited;
    static boolean[][] swanVisited;
    static List<Integer> swanPos = new ArrayList<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int result = 0;
    static boolean flag = false; // 두 백조가 만날 수 있으면 true

    public static boolean swanBFS(int x, int y) {
        swanVisited = new boolean[R][C];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        swanVisited[x][y] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0], cy = cur[1];

            for (int dir = 0; dir < 4; dir++) {
                int nx = cx + dx[dir];
                int ny = cy + dy[dir];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if (swanVisited[nx][ny]) continue;

                if (matrix[nx][ny] == 'L') return true;

                if (matrix[nx][ny] == '.') {
                    q.add(new int[]{nx, ny});
                    swanVisited[nx][ny] = true;
                }
            }
        }
        return false;
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();

        while (true) {
            visited = new boolean[R][C];

            // 백조 탐색 (매일 처음부터 다시 BFS)
            flag = swanBFS(swanPos.get(0), swanPos.get(1));
            if (flag) break;
            result++;

            // 하루가 지나면 전체 격자를 돌며 빙판 녹이기
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (matrix[i][j] == '.' && !visited[i][j]) {
                        q.add(new int[]{i, j});
                        visited[i][j] = true;

                        while (!q.isEmpty()) {
                            int[] cur = q.poll();
                            int cx = cur[0], cy = cur[1];

                            for (int dir = 0; dir < 4; dir++) {
                                int nx = cx + dx[dir];
                                int ny = cy + dy[dir];

                                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;

                                if (matrix[nx][ny] == 'X') {
                                    matrix[nx][ny] = '.';
                                    visited[nx][ny] = true;
                                }

                                if (matrix[nx][ny] == '.' && !visited[nx][ny]) {
                                    q.add(new int[]{nx, ny});
                                    visited[nx][ny] = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    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());

        matrix = new char[R][C];
        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                matrix[i][j] = line.charAt(j);
                if (matrix[i][j] == 'L') {
                    swanPos.add(i);
                    swanPos.add(j);
                }
            }
        }

        bfs();
        System.out.println(result);
    }
}

 

 

정답코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int R, C;
    static char[][] matrix;
    static boolean[][] visited;      // 물 확장 방문(재활용)
    static boolean[][] swanVisited;  // 백조 이동 방문
    static List<Integer> swanPos = new ArrayList<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int result = 0;

    static Queue<int[]> waterQ = new LinkedList<>();
    static Queue<int[]> nextWaterQ = new LinkedList<>();
    static Queue<int[]> swanQ = new LinkedList<>();
    static Queue<int[]> nextSwanQ = new LinkedList<>();

    // 두 백조가 만날 수 있으면 true
    public static boolean swanBFS(int x, int y) {
        while (!swanQ.isEmpty()) {
            int[] cur = swanQ.poll();
            int cx = cur[0], cy = cur[1];

            for (int dir = 0; dir < 4; dir++) {
                int nx = cx + dx[dir];
                int ny = cy + dy[dir];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if (swanVisited[nx][ny]) continue;

                // 다른 백조를 만난 경우 즉시 종료
                if (matrix[nx][ny] == 'L') return true;

                // 물이면 오늘 계속 이동
                if (matrix[nx][ny] == '.') {
                    swanQ.add(new int[]{nx, ny});
                    swanVisited[nx][ny] = true;
                }
                // 얼음이면 내일 시도 목록에 추가
                else if (matrix[nx][ny] == 'X') {
                    nextSwanQ.add(new int[]{nx, ny});
                    swanVisited[nx][ny] = true;
                }
            }
        }
        return false;
    }

    // 물의 경계에서만 얼음을 녹인다
    public static void melt() {
        while (!waterQ.isEmpty()) {
            int[] cur = waterQ.poll();
            int cx = cur[0], cy = cur[1];

            for (int dir = 0; dir < 4; dir++) {
                int nx = cx + dx[dir];
                int ny = cy + dy[dir];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if (visited[nx][ny]) continue;

                // 물이 새로 퍼질 수 있는 얼음이면 녹여서 내일의 물로
                if (matrix[nx][ny] == 'X') {
                    matrix[nx][ny] = '.';
                    nextWaterQ.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
                // 이미 물인 칸이면 오늘 물로 이어서 확장(경계 넓히기)
                else {
                    waterQ.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

    public static void bfs() {
        // 초기: 첫 번째 백조 위치에서 시작
        swanVisited = new boolean[R][C];
        int sx = swanPos.get(0), sy = swanPos.get(1);
        swanQ.add(new int[]{sx, sy});
        swanVisited[sx][sy] = true;

        // 하루 단위 반복
        while (true) {
            // 오늘 물 위에서 백조가 갈 수 있는 만큼만 이동
            if (swanBFS(sx, sy)) break;

            // 아직 못 만났다면 하루 경과
            result++;

            // 오늘 물의 경계에서 얼음을 녹임(내일 물 준비)
            melt();

            // 내일 준비된 큐로 교체
            waterQ = nextWaterQ;
            nextWaterQ = new LinkedList<>();

            swanQ = nextSwanQ;
            nextSwanQ = new LinkedList<>();
        }
    }

    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());

        matrix = new char[R][C];
        visited = new boolean[R][C];   // 물 확장 방문

        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                char ch = line.charAt(j);
                matrix[i][j] = ch;

                // 백조 위치 저장 (두 번 들어옴)
                if (ch == 'L') {
                    swanPos.add(i);
                    swanPos.add(j);
                    // 백조가 있는 칸도 물 취급
                    waterQ.add(new int[]{i, j});
                    visited[i][j] = true;
                } else if (ch == '.') {
                    // 초기 물들을 전부 물 큐에 넣고 방문 표시
                    waterQ.add(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        // 시뮬레이션 시작
        bfs();

        System.out.println(result);
    }
}

 

 

마무리하며:

이번 문제에서 사용된 BFS 방식은 내가 처음 접해본 구현 방법이었다. 초반에는 익숙하지 않아 블로그를 참고할 수밖에 없었지만, 과정을 따라가면서 새로운 탐색 패턴을 배울 수 있었다. 특히, 불필요하게 전 격자를 반복 탐색하는 대신, 경계선만 관리하는 큐 기반 BFS로 시간 복잡도를 획기적으로 줄이는 아이디어는 인상적이었다.

 

이러한 구현 방법을 익혀두면, 앞으로 비슷한 유형의 시뮬레이션 문제나 대규모 격자 그래프 탐색 문제를 풀 때 큰 도움이 될 것이다.

 

 

감사합니다.