[백준] 3197 백조의 호수 JAVA 이해하기 좋은 풀이^^

1. 문제 설명 📌

(1) 링크🔗

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

(2) 해설🕵

문제가 직관적이라서 패스

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: BFS + 오늘 BFS 돌릴 Queue과 내일 돌릴 Queue 구분!

언뜻 보면, 그냥 벽부수고 이동하기 같은 문제처럼 매번 BFS를 단순히 돌면 된다고 생각하기 쉽지만, 다음과 같은 조건 때문에 더 깊게 생각해봐야 한다.

• 행과 열의 최대가 1500이므로, 이렇게 풀면 시간초과가 난다.
• 하루가 구분되어, 정해진 양만큼만 BFS를 돈다.

필자의 경우 1번을 간과하여 시간초과를 냈으며, 두 번째를 간과하여 이후 틀렸습니다. 오류도 내었다. 자세한 트러블 슈팅은 현 포스팅 맨 하단에 기록해 두겠다.

따라서 방법은 다음과 같다.

매일 얼음 녹이기 관련

• 하루마다 녹는 얼음이 정해져 있기에 오늘 할당량 만큼만 BFS를 돌아야 한다.
  • 이를 위해 오늘 녹을 얼음 큐로 현 BFS를 진행하고, 내일 녹을 얼음들을 nextQ에 새로 담아놓는다.
  • 오늘의 큐만큼 BFS가 끝나면, 이제 다음 날이 밝을 것이므로 오늘의 큐는 nextQ로 대체된다.

백조 움직이기 관련

• 백조 또한 오늘 녹은 얼음까지만 더 갈 수 있다.
  • 오늘 갈 수 있는 최대치까지 간다.
  • 오늘의 경계선 (즉 얼음과 만나는 지점의 백조 좌표)를 내일의 큐에 집어넣는다.
  • BFS가 끝나면 오늘의 큐를 내일의 큐로 대체한다.

(2) SUDO CODE 📜

+ 0. init()
-    (1) 배열을 초기화 한다.
-    (2) 물인 지점, 백조가 존재하는 좌표는 각각 오늘의 얼음 녹이기 큐와 오늘의 백조 움직이기 큐에 집어 넣는다.
-    (3) 백조 두 개 구분해서 표시 (만났는지 아닌지 확인 위함)
+ 1. 다음을 반복해서 진행한다.
-    (1) 오늘 가능한 얼음을 녹인다.
-    (2) 오늘 가능한 백조를 움직인다.
-    (3) 백조 둘이 만났는가? 만나면 반복 탈출, 아니면 다시 1로 돌아감
+ 2. 답 출력
-    1번을 반복한 횟수를 출력



함수 소개
+ 1. 오늘의 얼음 녹이기
-    (0) 현 큐사이즈가 오늘 녹일 얼음의 양이므로, 그만큼만 BFS를 돈다.
-    (1) 물과 근접한 얼음을 만나면, 이제 이 곳이 내일의 출발점이 되므로 내일의 얼음 큐에 넣기
-    (2) 내일의 큐로 오늘의 큐를 갈음

+ 2. 오늘의 백조 움직이기
-    위와 얼음인지 백조인지만 다르지 로직 같음

(3) 시간복잡도 분석 🕓

위에서 이중 반복문을 했던 것과 달리 현 풀이는 얼음과의 접경지역 만 다시 누적해서 확인한다.
따라서 반복문 전체를 돌려도 배열 전체를 딱 한 번 확인하는 것이므로,

$$ O(R * C) $$

이다.

3. 구현 코드 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static int R, C;
    static char [][] field;
    static boolean [][] isVisited;
    static int [][] dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    static ArrayDeque<Coordinate> melting_spot = new ArrayDeque<>();
    static ArrayDeque<Coordinate> swan_1 = new ArrayDeque<>();


    static class Coordinate {
        int r;
        int c;

        public Coordinate (int r, int c){
            this.r = r;
            this.c = c;
        }
    }

    public static void main(String[] args) throws IOException {
        init();
        int cnt = 0;
        while (true) {
            cnt++;
            melting();
            if(swan_fill(true)) break;
        }
        System.out.println(cnt);

    }

    public static void init() 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());
        field = new char[R][C];
        isVisited = new boolean[R][C];
        int cnt = 0;
        for (int i = 0; i < R; i++) {
            String row = br.readLine();
            for (int j = 0; j < C; j++) {
                field[i][j] = row.charAt(j);
                if(row.charAt(j) != 'X') melting_spot.add(new Coordinate(i,j));
                if(row.charAt(j) == 'L') {
                    if(cnt == 0) {
                        field[i][j] = '1';
                        swan_1.add(new Coordinate(i,j));
                    }
                    else field[i][j] ='2';
                    cnt++;
                }
            }
        }
    }

    public static void melting() {
        int qSize = melting_spot.size();
        for (int i = 0; i < qSize; i++) {
            Coordinate now = melting_spot.poll();
            for (int j = 0; j < 4; j++) {
                int nextR = now.r + dir[j][0];
                int nextC = now.c + dir[j][1];
                if(!OOB(nextR,nextC) && field[nextR][nextC] == 'X'){
                    field[nextR][nextC] = '.';
                    melting_spot.add(new Coordinate(nextR, nextC));
                }
            }
        }
    }

    public static boolean swan_fill(boolean isOne) {
        char fill = '1';
        char opposite ='2';
        ArrayDeque<Coordinate> now_aq1 = swan_1;
        ArrayDeque<Coordinate> next_aq = new ArrayDeque<>();

        while (!now_aq1.isEmpty()) {
            Coordinate now = now_aq1.poll();
            for (int i = 0; i < 4; i++) {
                int nextR = now.r + dir[i][0];
                int nextC = now.c + dir[i][1];
                if(!OOB(nextR,nextC)&& !isVisited[nextR][nextC] &&field[nextR][nextC] != 'X') {
                    if(field[nextR][nextC] != opposite){
                        field[nextR][nextC] = fill;
                        isVisited[nextR][nextC] = true;
                        now_aq1.add(new Coordinate(nextR,nextC));
                    }else {
                        return true;
                    }
                }
                if ((!OOB(nextR,nextC)&& !isVisited[nextR][nextC] &&field[nextR][nextC] == 'X')){
                    isVisited[nextR][nextC] = true;
                    next_aq.add(new Coordinate(nextR,nextC));
                }
            }
        }
        swan_1 = next_aq;
        return false;
    }

    public static boolean OOB (int r, int c) {
        return !(r >= 0 && r < R && c >= 0 && c < C);
    }
}

4. 배운 것들 🎯

내가 틀리게 생각했던 과정과 그것이 틀린 이유 트러블 슈팅을 적어놓겠다.

A. 첫 풀이 (시간 초과)

다음과 같이 모듈화 해서 풀었다.

+ 1. 초기화 함수
+ 2. 물 근접 얼음 찾기 함수 
-    (1) 이중 for 문 루프 돌면서 . 찾으면 거기서 부터 BFS, 얼음 만나면 'N'
+ 3. 물 근접 얼음 녹이기 함수
-    (1) 이중 for 문 돌면서 N을 .으로 바꾸기 (이러지 않으면 BFS가 이전 BFS 녹인 거 중첩해서 다 지워버림)
+ 4. 백조끼리 닿는지 확인하는 함수
+ 5. 2~4번을 백조끼리 만날 떄까지 반복 -> 만나면 지금까지의 반복 횟수 출력

시간 초과 났다. 시간복잡도를 계산해보면 다음과 같다.

• 2,3,4가 연속적이진 않더라도 전부 $O(R*C)$
• 이걸 백조끼리 만나는 날까지 반복 $O(log(R*C))$
• R*C 는 최대 2,250,000 개이다.
• 따라서 최종 빅오는 O(log(RC) * RC)가 되므로 $10^9$ ~ $10^{10}$ 사이이다.

B. 두번째 풀이 (틀림)

이번엔 방법을 바꿔서 다음과 같이 풀었다.

+ 1. 초기화
-    (1) 초기화 시, swan_fill 함수를 통해, 최초 시점에서 swan이 갈수 있는 곳까지 체크 (양쪽에서 전부) 
-        얼음 경계지점에 있는 백조의 가능한 좌표를 전부 swan_1, swan_2 큐에 구분해서 집어넣는다.
-    (2) 자신의 좌표는 얼음이면서 사방 탐색 시 백조나 물이 있다? -> 녹을 얼음 = melting_spot 큐에 집어넣는다.

+ 2. 다음을 반복
- (1) 물 근접 얼음 녹이기 함수: 최초 큐 크기만큼만 BFS 진행 (금방 meltiong_spot에 들어가 있는 걸 녹이고, 녹은 거 기준 또 근접한 것을 queue 에 넣음)
- (2) 백조 두마리 이동시키기 함수: 금방 1-(1)에서 집어넣었던 백조의 좌표로 BFS, 더 갈 수 있는 곳 체크 
-        (큐 크기만큼만 진행 + 얼음 인접 백조는 또 다시 queue에 넣는다.)
- (3) 만약 (2) 하다가 만나면 함수 종료, 현재까지 반복횟수 출력

해당 방법은 다음과 같은 이유로 틀렸다.

• 현재 작업 중인 큐에 현재 작업해야 하는 거, 다음날 작업해야 하는 거 혼용해서 넣음 -> 이 때문에 오류가 잘 일어남.
• 백조 기준, 얼음 만날 때까지 BFS 도는 함수, 현 큐 사이즈만큼만 도는 함수 따로 만들어서 사용 -> 복잡도 올라감

이모지 모음: 🤔, ➜ ✨ 0️⃣1️⃣2️⃣3️⃣4️⃣5️⃣6️⃣7️⃣8️⃣9️⃣🔟