백준 2573번

 

bfs 배우니까 신세계가 따로 없다.

뭐 말로는 dfs로 풀 수 있는 건 bfs로 풀 수 있는데

bfs로 풀 수 없는 건 dfs로 풀 수 없다니까 bfs라도 잘 알아놓고 가자.

 

일단 그래프를 만든다. 하지만 여기는 동서남북 모든 노드의 정보를 알아야 하기 때문에 테두리를 둘러줘야한다.

그래서 그래프의 넓이를 n+1이 아닌 n+2로 만들어준다.

why? 1에서 n까지가 행과 열의 넓이라고 가정해보자

	1	1	1	1	1	1
	1	1	1	11	11	1
	1	1	1	11	1	1
	1	1	1	1	1	111
	1	1	1	1	1	1

 

1이 들어가있는 노드가 그래프의 시작이라고 가정하자.  시간의 흐름을 옆 노드를 기준으로 반영하기 위해서는 위, 아래, 좌, 우 노드가 모두 있어야만 한다. (그렇지 않다면 첫 번째 인덱스를 돌다가  index out of bound Exception이 등장한다,)

그래서 길이를 n+2로 잡아서 그냥 없는 노드를 만들어줬다.

 

 

이건 시간의 흐름 + bfs로 해서

1. 모든 노드의 for 문을 돌려서

2. 해당 노드를 방문하지 않았다면 bfs를 실행하고 카운트++ 를 해준다.

 

3. 만일 count가 2 이상이라면 떨어져있는 빙산이 존재한다는 것이기 때문에 해당 year를 출력해준다.

4. 만일 count가 0이 나왔다면 모든 빙산이 녹았다는 것이기 때문에 0을 return해준다. (year 출력해주면 이상한 수가 나오기 때문에 if else문으로 걸어주자)

 

시간의 흐름같은 경우에는 oneYearLater 함수를 따로 만들어서 돌렸다.

 

다만 한가지 주의사항이 있다.

물론 년도를 한번 돌려서 진행할 때 방문을 초기화 해주는 것은 당연하다.

이와 별개로 큰 반례가 있는데,

만약에 oneYearLater 함수에서 원본을 바로 2중 for문으로 수정한다고 가정했을 때

5 7
0 0 0 0 0 0 0
0 10 10 10 10 10 0
0 10 0 1 0 10 0
0 10 10 10 10 10 0
0 0 0 0 0 0 0

이렇게 된 반례가 등장한다면

위쪽 3번째 10에서는 아래 1이 존재하기 때문에 9가 된다. 그리고 계속 iterator를 돌다가  3 번째 행의 1이 나오면 -> 0이 된다.

하지만 그 아래 10에서는 위 행이 1이 아닌 0이기 때문에 8이 되어버린다.

 

그래서 deepcopy를 하고 이를 수정한 다음에 원본 그래프에다가 deepcopy한 그래프의 주소값으로 바꿔치기 하는 방식을 이용하면서 문제를 해결할 수 있었다.

 

 

 

그대로 돌리지말고 package 수정해주고 class 명 Main으로 바꿔주자.

package programers;

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

public class BOJ2573 {
    static int[][] graph;
    static boolean[][] visited;
    static int[][] all = new int[][] {{-1,0}, {0,1}, {0,-1}, {1,0}}; // 동서남북

    public static int[][] deepCopy(int[][] original) { 
    // 딥카피 만들기 귀찮아서 챗지피티 썼다.
        if (original == null) return null;
        int[][] result = new int[original.length][];
        // for문 하나하나 돌면서 어레이 카피를 해준다. gpt 피셜 저 메소드가 제일 효율적이라고 한다.
        for (int i = 0; i < original.length; i++) { 
            result[i] = new int[original[i].length];
            System.arraycopy(original[i], 0, result[i], 0, original[i].length);
        }
        return result;
    }

    public static int[][] oneYearsLater(int n, int m) {
        int[][] copy = deepCopy(graph);  // 원본 바로 수정하면 안된다.
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < m+1; j++) {
                int count = 0;
                for (int[] direction: all) { // 동 서 남 북 이 바다라면 count++ 해준다. 최대값 4
                    if (graph[i + direction[0]][j + direction[1]] == 0) {
                    // copy는 수정되고 있으니까 원본인 graph로 비교 해줘야한다.
                        count++;
                    }
                }
                copy[i][j] -= count;
                copy[i][j] = Math.max(0, copy[i][j]); // 음수로 나올수도 있으니까 max해주기
            }
        }
        return copy;
    }

// bfs 이용한 빙산 몇갠지 알려주는 함수
    public static int solution(int n, int m) {
        int count = 0;
        // 모든 노드를 다 돈다.
        for(int i = 1; i < n+1; i++) {
            for (int j = 1; j < m+1; j++) {
                if (graph[i][j] > 0 && !visited[i][j]) {
                    Queue<int []> q = new LinkedList();
                    q.add(new int[] {i,j});
                    visited[i][j] = true;
                    count++;

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


                        for (int[] direction: all) {
                            if (graph[now[0] + direction[0]][now[1] + direction[1]] > 0 && !visited[now[0] + direction[0]][now[1] + direction[1]]) {
                                q.add(new int[] {now[0] + direction[0],now[1] + direction[1]});
                                visited[now[0]+direction[0]][now[1]+direction[1]] =true;
                            }
                        }
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        graph = new int[n + 2 ][m + 2];
        visited = new boolean[n+2][m+2];

        for (int i = 1; i < n+1; i++) {
            for(int j = 1; j < m+1; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        int ans;
        int year = 0;
        while(true) {
        // 방문여부 초기화
        // 처음에는 new int[][]로 했는데 메모리 초과나서 이렇게 바꿔줬다.
        // 이중포문으로 하는거랑 시간복잡도는 같지 않을까 싶다.
            for (boolean[] vi: visited) {
                Arrays.fill(vi, false);
            }
                if (year > 0) {
                graph = oneYearsLater(n, m);
                }
			// ans = 빙산의 개수
            ans = solution(n,m);
            if (ans >= 2 || ans == 0) break;
            year++;
        }
        if(ans >= 2) {
        System.out.println(year);
        } else {
        // 여기는 그냥 0 출력해줘도 된다. 마침 ans가 0이길래 ans로 출력해줬을 뿐
        System.out.println(ans);
        }
    }
}