[백준] 3197번 백조의 호수

문제 설명

https://www.acmicpc.net/problem/3197

문제 풀이

• 최적화가 필요한 BFS 문제이다. (1500x1500 맵 크기)

• 다음 2가지 bfs를 사용하여 풀이하였다.

  1. meltProcess() : 각 위치의 얼음이 몇일차에 녹는지 2차원 배열에 만들어준다.
  2. moveSwan() : 날이 진행되며 백조가 이동할 수 있는지 여부를 확인하고 결과 출력.

• 최적화를 위해 고려했던 점은 다음과 같았다.

  1. 얼음이 날짜별로 녹는 것에 대해 녹았던 곳에 대한 반복을 없애기
  2. 백조 이동가능 여부를 확인할 때, 이전 날짜에 백조 이동에 대한 반복을 없애기

• 위 둘중 하나라도 안했을 경우 시간초과가 났던걸로 기억..

소스 코드 (JAVA)

package com.company;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static class Status {
        int x, y, time;

        public Status(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
    public static int sX, sY, tX, tY, R, C, result;
    public static char[][] map = new char[1501][1501];
    public static int[][] meltMap = new int[1501][1501];
    public static boolean[][] chk = new boolean[1501][1501];
    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};

    //얼음이 녹는 것 시뮬레이션
    public static void meltProcess() {
        //BFS 시작
        Queue<Status> queue = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                meltMap[i][j] = Integer.MAX_VALUE;
                if (map[i][j] == '.') {
                    meltMap[i][j] = 0;
                    queue.add(new Status(i, j, 0));
                }
            }
        }
        while(!queue.isEmpty()) {
            Status cur = queue.poll();
            for (int d = 0; d < 4; d++) {
                int X = cur.x + dx[d];
                int Y = cur.y + dy[d];
                if (X < 0 || Y < 0 || X >= R || Y >= C || meltMap[X][Y] <= cur.time + 1)
                    continue;
                meltMap[X][Y] = cur.time + 1;
                queue.add(new Status(X, Y, cur.time + 1));
            }
        }
    }

    //날짜 별 백조 이동 시뮬레이션
    public static void moveSwan() {
        Queue<Status> queue1 = new LinkedList<>();
        Queue<Status> queue2 = new LinkedList<>();
        chk[sX][sY] = true;
        queue2.add(new Status(sX, sY, 0));
        while(true) {
            //갈 수 있는 지점 기억해줌
            while(!queue2.isEmpty()) {
                queue1.add(queue2.poll());
            }
            while(!queue1.isEmpty()) {
                Status cur = queue1.poll();
                for (int d = 0; d < 4; d++) {
                    int X = cur.x + dx[d];
                    int Y = cur.y + dy[d];
                    if (X < 0 || Y < 0 || X >= R || Y >= C || chk[X][Y] == true)
                        continue;
                    //현재 시점으로는 갈 수 없는 곳 -> 다음 큐에 넣어줌
                    if (meltMap[X][Y] == cur.time + 1) {
                        chk[X][Y] = true;
                        queue2.add(new Status(X, Y, cur.time + 1));
                    }
                    //현재 시점에 갈 수 있는 곳 -> 현재 큐에 넣어줌
                    else if (meltMap[X][Y] <= cur.time){
                        chk[X][Y] = true;
                        queue1.add(new Status(X, Y, cur.time));
                        if (X == tX && Y == tY) {
                            result = cur.time;
                            return;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt(); C = sc.nextInt();
        sX = -1;
        for (int i = 0; i < R; i++) {
            String temp = sc.next();
            for (int j = 0; j < C; j++) {
                map[i][j] = temp.charAt(j);
                if (map[i][j] == 'L') {
                    map[i][j] = '.';
                    if (sX == -1) { sX = i; sY = j; }
                    else { tX = i; tY = j; }
                }
            }
        }
        meltProcess();
        moveSwan();
        System.out.println(result);
    }
}