[백준] 3197. 백조의 호수

문제 링크

[백준] 3197. 백조의 호수

풀이 과정

시간 초과를 방지하기 위해 백조의 BFS 탐색과 물 확장을 동시에 진행해주어야 했습니다. 또한, BFS 탐색은 다음날이 되어 새롭게 이동 가능한 좌표들만으로 진행해주어야 합니다.

1. 현재 백조가 이동 가능한 좌표들을 확인하며, 인접한 빙판 영역(주황색)을 큐에 담아둡니다.
2. 1에서 이동 가능한 좌표에 다른 백조가 위치한다면, 더이상 반복하지 않고 종료합니다.
3. 백조의 이동 가능한 영역을 체크해둔 인접한 빙판 영역(주황색)으로 바꿔줍니다.
4. 기존 물의 좌표를 담아둔 큐의 사이즈만큼 하나씩 뽑아가며, 해당 물과 인접한 빙판들을 물로 바꿔주고, 큐에 새로 담아줍니다. (이 작업에서 물의 좌표를 담아둔 큐는 다음 날 확인해봐야 할 새로운 물의 좌표들만 남게됩니다.)

static int R, C;
static char[][] map;
static boolean[][] visit;
static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
static Queue<int[]> water, swan;
static ArrayList<int[]> swanPos;
static int day;

문제 풀이에 사용된 전역변수들입니다. 큐로 설정된 water 와 swan 은 각각 물의 좌표와 백조의 이동 가능한 좌표를 담아두기 위해 사용됩니다.

for (int i = 0; i < R; i++) {
    String s = sc.next();
    for (int j = 0; j < C; j++) {
        char ch = s.charAt(j);
        map[i][j] = ch;

        if (ch == 'L') {
            swanPos.add(new int[]{i, j});
            map[i][j] = '.';
            water.add(new int[]{i, j});
        } else if (ch == '.') {
            water.add(new int[]{i, j});
        }
    }
}

먼저 입력을 받습니다.

• L 은 백조의 위치를 의미하므로, swanPos 리스트에 담아줍니다. 또한, 백조는 물 위에 떠 있으므로, 백조가 있는 좌표도 결국 물이 됩니다. 따라서, water 리스트에도 해당 좌표를 추가해줍니다.
• . 은 물을 의미하므로, water 리스트에 좌표를 담아줍니다.

int[] start = swanPos.get(0);
visit[start[0]][start[1]] = true;
swan.add(start);

백조 두 마리의 좌표를 담고 있는 swanPos 리스트에서 0번째 좌표 하나를 꺼내 시작 지점으로 설정합니다. 이 좌표에 대한 방문 처리를 한 후, swan 큐에 담아 BFS 탐색을 준비합니다.

while (true) {
	...
}

이제 답을 구할때까지 루프를 계속 돕니다. 루프 안의 코드는 아래에 분리해서 설명하겠습니다.

boolean exitFlag = false;
Queue<int[]> next = new LinkedList<>();

while (!swan.isEmpty()) {
    int[] now = swan.poll();

    if (now[0] == swanPos.get(1)[0] && now[1] == swanPos.get(1)[1]) {
        exitFlag = true;
        break;
    }

    for (int d = 0; d < 4; d++) {
        int nx = now[0] + dx[d], ny = now[1] + dy[d];

        if (!inRange(nx, ny) || visit[nx][ny]) continue;

        visit[nx][ny] = true;
        if (map[nx][ny] == '.') swan.add(new int[]{nx, ny});
        else if (map[nx][ny] == 'X') next.add(new int[]{nx, ny});
    }
}

if (exitFlag) break;

먼저 백조가 이동 가능한 경로들에 대해 아래 작업을 수행합니다.

• 백조의 이동 경로에 다른 백조가 존재하면, exitFlag 를 설정해 무한 루프에서 빠져나옵니다.
• 이동할 좌표에 물( . )이 위치하면, swan 큐에 넣어 이동을 계속합니다.
• 이동할 좌표에 빙판( X )이 위치하면, 초기에 비어있는 큐로 설정한 next 큐에 저장해둡니다.

swan = next;
int waterSize = water.size();

while (waterSize-- > 0) {
    int[] now = water.poll();

    for (int d = 0; d < 4; d++) {
        int nx = now[0] + dx[d], ny = now[1] + dy[d];

        if (!inRange(nx, ny)) continue;
        if (map[nx][ny] == 'X') {
            map[nx][ny] = '.';
            water.add(new int[]{nx, ny});
        }
    }
}

day++;

이제 물을 확장시킬 차례입니다. 제일 먼저, next 큐를 swan 변수에 담아, 가리키는 큐의 주소를 바꿔줍니다. 다음으로, water 큐의 크기 waterSize 개수만큼 좌표를 뽑아내며 인접한 빙판을 물로 바꿔주고 동시에 큐에 새로 담아줍니다. 물을 확장시켰으니 day 를 증가시켜 날짜를 반영해줍니다.

코드

import java.util.*;

public class Main {
    static int R, C;
    static char[][] map;
    static boolean[][] visit;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static Queue<int[]> water, swan;
    static ArrayList<int[]> swanPos;
    static int day;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        map = new char[R][C];
        visit = new boolean[R][C];
        water = new LinkedList<>();
        swan = new LinkedList<>();
        swanPos = new ArrayList<>();

        for (int i = 0; i < R; i++) {
            String s = sc.next();
            for (int j = 0; j < C; j++) {
                char ch = s.charAt(j);
                map[i][j] = ch;

                if (ch == 'L') {
                    swanPos.add(new int[]{i, j});
                    map[i][j] = '.';
                    water.add(new int[]{i, j});
                } else if (ch == '.') {
                    water.add(new int[]{i, j});
                }
            }
        }

        int[] start = swanPos.get(0);
        visit[start[0]][start[1]] = true;
        swan.add(start);

        while (true) {
            boolean exitFlag = false;
            Queue<int[]> next = new LinkedList<>();

            while (!swan.isEmpty()) {
                int[] now = swan.poll();

                if (now[0] == swanPos.get(1)[0] && now[1] == swanPos.get(1)[1]) {
                    exitFlag = true;
                    break;
                }

                for (int d = 0; d < 4; d++) {
                    int nx = now[0] + dx[d], ny = now[1] + dy[d];

                    if (!inRange(nx, ny) || visit[nx][ny]) continue;

                    visit[nx][ny] = true;
                    if (map[nx][ny] == '.') swan.add(new int[]{nx, ny});
                    else if (map[nx][ny] == 'X') next.add(new int[]{nx, ny});
                }
            }

            if (exitFlag) break;

            swan = next;
            int waterSize = water.size();

            while (waterSize-- > 0) {
                int[] now = water.poll();

                for (int d = 0; d < 4; d++) {
                    int nx = now[0] + dx[d], ny = now[1] + dy[d];

                    if (!inRange(nx, ny)) continue;
                    if (map[nx][ny] == 'X') {
                        map[nx][ny] = '.';
                        water.add(new int[]{nx, ny});
                    }
                }
            }

            day++;
        }

        System.out.println(day);
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > R - 1 || y < 0 || y > C - 1) return false;
        return true;
    }
}