백준 3197번 - 백조의 호수

🎯 중복된 연산을 줄일 방법을 찾자

1차 풀이

처음 생각했던 로직은 다음과 같다
1. swan 끼리 만날 수 있는지 판단하는 bfs (map 이 바뀔 때마다 bfs 진행)
2. map 에서 얼음을 녹이는 bfs (해당 턴에서 녹은 'X' 위치를 매번 큐에 넣기)

위와 같이 진행한다면 시간초과를 만나게 된다
그 이유로는 매번 bfs 를 진행하는데 있다. 최악의 경우 약 1500*O(RC) 가 된다. (swan 이 끝과 끝에 있고 모두 얼음인 경우)

잠시 2차원 배열에서의 bfs 시간복잡도를 잡고 가도록 하자

2차원 배열에서의 bfs 시간복잡도
가로가 R, 세로가 C 라 할 때 각 점에서 연결될 수 있는 간선은 총 4개이다. (모서리는 생략해서 생각하자) 그렇다면 bfs 시간복잡도는 O(V+E) 이므로 O(RC + 4RC) 이므로 O(RC) 가 된다 (상수배 생략)

2차 풀이

따라서 매번 bfs 를 진행하는 것이 아닌 다른 방법이 필요했다. 이 때 bfs 를 매번 연산하는 것은 중복된 연산임을 파악하고 중복된 연산을 줄이고자 생각했다. 그러기 위해서는 현재에서 얼음 위치를 큐에 넣고 큐를 남기는 방식을 통해 bfs 자체는 결국 1번만 진행하는 것이 중복을 줄이는 연산임을 알게 되었다

최종 코드

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

public class Main {
    static int R, C;
    static char[][] map;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static List<int[]> swanInitPosition = new ArrayList<>();
    static Queue<Cor> waterQueue = new LinkedList<>();
    static Queue<Cor> swanQueue = new LinkedList<>();
    static boolean[][] isVisited;
    static int startX, startY, endX, endY;

    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());
        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        // 백조 1, 2 위치 찾기 + waterQueue 에 '.' 위치 넣기
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'L') {
                    int[] p = new int[]{i, j};
                    swanInitPosition.add(p);
                    waterQueue.add(new Cor(i, j));
                } else if (map[i][j] == '.') {
                    waterQueue.add(new Cor(i, j));
                }
            }
        }

        startX = swanInitPosition.get(0)[0];
        startY = swanInitPosition.get(0)[1];
        endX = swanInitPosition.get(1)[0];
        endY = swanInitPosition.get(1)[1];

        // 최적화된 bfs 탐색 -> map 변화
        int day = 0;
        swanQueue.add(new Cor(startX, startY));
        isVisited = new boolean[R][C];
        isVisited[startX][startY] = true;

        while (!swanCanMeet()) {
            iceMelt();
            day++;
        }
        System.out.println(day);
    }

    public static boolean swanCanMeet() {
        Queue<Cor> nextSwanQueue = new LinkedList<>();
        while (!swanQueue.isEmpty()) {
            Cor swanCurrent = swanQueue.poll();
            if (swanCurrent.x == endX && swanCurrent.y == endY) return true;
            for (int d = 0; d < 4; d++) {
                int nextX = swanCurrent.x + dx[d];
                int nextY = swanCurrent.y + dy[d];
                if (nextX < 0 || nextX >= R || nextY < 0 || nextY >= C || isVisited[nextX][nextY]) continue;
                isVisited[nextX][nextY] = true;
                if (map[nextX][nextY] == 'X') {
                    nextSwanQueue.add(new Cor(nextX, nextY));
                } else {
                    swanQueue.add(new Cor(nextX, nextY));
                }
            }
        }
        swanQueue = nextSwanQueue;
        return false;
    }

    public static void iceMelt() {
        Queue<Cor> nextWaterQueue = new LinkedList<>();
        while (!waterQueue.isEmpty()) {
            Cor waterCurrent = waterQueue.poll();
            for (int d = 0; d < 4; d++) {
                int nextX = waterCurrent.x + dx[d];
                int nextY = waterCurrent.y + dy[d];
                if (nextX < 0 || nextX >= R || nextY < 0 || nextY >= C || isVisited[nextX][nextY]) continue;
                if (map[nextX][nextY] == 'X') {
                    map[nextX][nextY] = '.';
                    nextWaterQueue.add(new Cor(nextX, nextY));
                }
            }
        }
        waterQueue = nextWaterQueue;
    }
}
class Cor {
    int x;
    int y;

    public Cor(int x, int y) {
        this.x = x;
        this.y = y;
    }
}