백준 2573 빙산 - JAVA

2573 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

<빙산 조각 탐색과 빙산의 녹는 양 계산이 분리된 풀이> - 일반적인 탐색 틀에 맞춘 풀이, 직관적

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int[][] map;
    static int[][] temp;
    static boolean[][] visit;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            } 
        }
        int year = 0;
        while(true) {
            int piece = 0;
            melting();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (visit[i][j] || map[i][j] == 0) continue;
                    dfs(i, j);
                    piece++;
                } 
            }
            year++;
            if (piece >= 2) break; 
            if (piece == 0) {
                year = 0;
                break;
            }
        }
        bw.write(String.valueOf(year));
        bw.flush();
    }
    private static void melting() {
        temp = new int[N][M];
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int count = 0;
                for (int d = 0; d < 4; d++) {
                    int ni = i + dx[d];
                    int nj = j + dy[d];
                    if (ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
                    if (map[ni][nj] <= 0) count++;
                } 
                temp[i][j] = map[i][j] - count > 0 ? map[i][j] - count : 0;
            } 
        } 
        for (int i = 0; i < N; i++) {
            map[i] = Arrays.copyOf(temp[i], M);
        } 
    }
    private static void dfs(int x, int y) {
        visit[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (visit[nx][ny] || map[nx][ny] == 0) continue; 
            dfs(nx, ny);
        } 
    }
}

 

<빙산 조각 탐색과 빙산의 녹는 양 계산을 동시에 수행하는 풀이> - 효율적인 탐색 풀이, 코드 복잡도 ⬆️

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int[][] map;
    static int[][] visit;
    static Queue<int[]> queue;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visit = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            } 
        }
        int year = 0;
        while(countIsland() == 1) {
            int zeroCount = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    // 미리 계산된 visit을 활용해 다음 맵 갱신
                    if (visit[i][j] != -1) map[i][j] = Math.max(map[i][j] - visit[i][j], 0);
                    if (map[i][j] == 0) zeroCount++; 
                } 
            }
            // 모두 녹아버리면 year는 0으로
            if (zeroCount == N * M) {
                year = 0;
                break;
            } 
            year++;
        }
        bw.write(String.valueOf(year));
        bw.flush();
    }
    private static int countIsland() {
        int count = 0;
        for (int i = 0; i < N; i++) {
            Arrays.fill(visit[i], -1);
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0 || visit[i][j] != -1) continue;
                bfs(i, j);
                count++;
            } 
        } 
        return count;
    }
    private static void bfs(int x, int y) {
        queue = new ArrayDeque<>();
        queue.offer(new int[] {x, y});
        visit[x][y] = countSea(x, y);
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (visit[nx][ny] != -1 || map[nx][ny] == 0) continue; 
                visit[nx][ny] = countSea(nx, ny); // 다음 번 맵 변경 시 얼마나 빼야하는지 계산
                queue.offer(new int[] {nx, ny});
            } 
        }
    }
    private static int countSea(int x, int y) {
        int count = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (map[nx][ny] != 0) continue;
            count++; 
        } 
        return count;
    }
}

 

알고리즘 설명

---

설명에 앞서, 주어진 문제를 두 번째 풀이로 접근했다면 컴퓨팅 사고에 최적화된 방식으로 사고했다고 말씀드리고 싶습니다.

저는 첫 번째 풀이로 생각보다 수월하게 문제를 해결했고, 대부분의 사람들이 그렇듯 탐색 알고리즘은 일정한 유형에 맞춰 풀린다고 여겨왔습니다. 그런데 백준 채점현황을 보다가 두 번째 풀이를 접하면서 제 사고의 틀이 깨지는 경험을 하게 되었습니다.

 

해당 문제는 BFS던 DFS던 모든 배열의 원소를 반복문으로 순회해야 하기 때문에 효율성의 차이는 크게 나지 않는다고 볼 수 있습니다. 굳이 따지자면 N * M이 최대로 커지는 경우 DFS가 300 * 300으로 재귀의 깊이가 9만 번까지 내려갈 수 있으므로, BFS가 오버플로우에서 안전하다... 정도가 될 수 있겠네요.

 

그러면 이제 제가 쉽게 풀었던 첫 번째 문제 풀이를 설명드리겠습니다. 첫 번째 풀이의 전반적인 흐름은 익히 알듯이 일반적인 탐색 풀이 틀에 맞추어 푸는 방식입니다. 조금 더 자세하게 설명드리면, 각 빙산 칸은 4방향의 바다 칸 수만큼씩 녹습니다. 문제는 탐색하면서 map을 바로 갱신하면, 앞서 처리한 칸이 이미 줄어든 영향으로 아직 처리하지 않은 이웃 칸의 바다 개수 계산에 영향을 주어 의도와 다른 결과가 나올 수 있다는 점입니다. 따라서 temp[][] 배열을 선언하고, melting()메서드에서 temp[][] 배열에 map[][] 배열의 다음 해의 빙산 높이를 저장하고, 루프가 끝난 뒤에 다시 temp[][] 배열을 map[][] 배열에 다시 입혀주어, map[][] 배열을 갱신하고 갱신된 map[][] 배열을 통해

빙산의 개수가 처음으로 2개 이상이 되는 햇수를 찾는 방식입니다.

 

두 번째 풀이입니다. 두 번째 풀이는 제가 혼자서 푼 건 아니지만, 나름 완벽하게 이해했기 때문에 적어보겠습니다.

두 번째 풀이는 visit[][] 배열을 탐색을 위한 방문에만 활용하는 것이 아닌 다음 해의 빙산이 얼마나 녹을지 높이도 기록합니다. 따라서 boolean이 아닌 int형으로 배열을 선언하고 각 원소를 -1 (방문하지 않음)로 설정합니다. BFS로 연결된 덩어리를 탐색하면서, 방문하지 않은 칸이면 visit[x][y]에 countSea(x, y)를 기록하고 큐에 넣습니다. 이렇게 하면 탐색과 동시에 다음 해 상태를 countSea()를 통해 계산할 수 있어, temp 배열을 별도로 만들 필요가 없습니다. BFS가 끝나면 visit 배열을 참조해 map 배열을 한 번에 갱신하고, 이후 덩어리 개수를 세어 빙산이 처음으로 두 덩어리 이상으로 나뉘는 시점을 판단합니다.

해당 풀이의 핵심은 탐색과 다음 해의 빙산이 녹는 양 계산을 한 번의 순회로 처리하여 불필요한 반복을 제거하는 것 입니다.

 

끝으로 풀이 별 메모리 사용량과 실행시간을 확인하며 마치겠습니다. 확실히 visit[][] 배열을 두 가지 용도로 사용하며 재활용까지 한 풀이가 꽤나 실행시간이나 메모리적으로 효율적인 풀이라는 것을 알 수 있습니다.

아래부터 <탐색과 녹는양 계산 따로한 풀이>, <탐색과 녹는양 계산을 동시에 한 풀이>

 

이런 효율적인 풀이들을 볼 때 마다, 아직 갈 길이 참 멀구나... 느낍니다. 뭐 저도 나쁘게 푼 건 아니지만 ㅎㅎ...

 

코드 해석

---

두 번째 풀이 방식을 기준으로 설명합니다.

먼저 map[N][M] 배열에 각 칸의 빙산 높이를 저장하고, 반복문을 통해 빙산이 두 개 이상으로 나뉘거나 모두 녹을 때까지 매 해를 진행합니다. 각 해에서는 먼저 countIsland() 메서드를 호출해 BFS로 연결된 빙산 덩어리 수를 센 뒤, 각 빙산 칸의 주변 4방향 바다 칸 개수를 계산하여 visit[][]에 기록하고, 이를 이용해 다음 해의 빙산 높이를 map[][]에 갱신합니다. BFS에서는 큐에 현재 칸 좌표를 넣고 꺼내면서 상하좌우 인접 칸을 확인하며, 이미 방문했거나 바다인 칸은 건너뛰고 아직 방문하지 않은 빙산 칸만 큐에 넣어 탐색합니다. 반복문이 끝나면 갱신된 map[][]을 기준으로 다시 countIsland()를 통해 덩어리 수를 확인하고, 빙산이 두 덩어리 이상이면 종료하며 그 해 수를 출력하고, 모든 빙산이 녹으면 0을 출력합니다.

 

핵심은 countIsland()와 bfs()를 통해 덩어리 수 확인과 다음 해 녹는 양 계산을 동시에 수행하고, visit[][] 배열을 활용해 반복문과 계산을 최소화함으로써 효율적인 탐색을 구현하는 것입니다.