백준 2573번 빙산 :: 마이구미

이번 글은 백준 알고리즘 2573번 "빙산" 을 다뤄본다.

정답 비율이 20%대로 어렵게 보이지만 비율 대비 쉬운 문제가 된다.

본인은 DFS를 통해 문제를 풀이하겠다.

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

문제를 보다시피, 1년이 지날 수록, 빙산의 높이가 상하좌우에 있는 0의 횟수만큼 줄어드는 것을 볼 수 있다.

그리고 그림3과 같이 2개 이상으로 분리되는 시점을 찾는 문제이다.

분리된 빙산은 {3, 2}, {3}, {4} 가 된다.

그래프에서 이러한 빙산의 영역을 "연결 요소"라고 표현한다.

즉, 이 문제는 연결 요소의 개수를 2개 이상이 되는 시점을 찾는 문제가 된다.

코드 흐름은 아래 과정을 반복하면 된다.

1. 연결 요소 개수 구하기 (2개 이상일 때 종료)
2. 빙산 녹이기

연결 요소의 개수를 찾기 위해서는 각 정점을 기준으로 DFS의 탐색 횟수를 구하면 된다.

왜냐하면, DFS는 한번 탐색을 시작하면 시작 정점을 기준으로 깊이 탐색한다.

그렇다는 건, 한번의 DFS 탐색은 하나의 연결 요소를 찾는 과정이 된다.

public static int componentNumber() {
    int component = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && map[i][j] > 0) {
                ++component;
                dfs(i, j);
            }
        }
    }
    return component;
}

그리고 빙산을 녹이기 위한 작업이 필요하다.

public static int nextYear(int y, int x) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int nx = dx[i] + x;
        int ny = dy[i] + y;

        if (0 <= ny && ny < n && 0 <= nx && nx < m) {
            if (map[ny][nx] <= 0 && map[y][x] > 0) {
                ++cnt;
            }
        }
    }
    return cnt;
}

단순히 상하좌우의 0을 카운트한 후, 카운트된 수를 빙산의 높이에 빼면 된다.

이 과정을 연결 개수가 2개 이상 나올 때까지 반복하면 된다.

코드가 조금 길어보이지만, 하나하나 살펴보면 어려운 코드가 아니다.

문제는 정답 비율에 비해 굉장히 쉬운 문제이니 풀어보길 바란다.

static int[][] map = new int[301][301];
static int[][] temp = new int[301][301];
static boolean[][] visited = new boolean[301][301];
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static int n, m;
 
private void solve() {
    n = sc.nextInt();
    m = sc.nextInt();
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            map[i][j] = sc.nextInt();
        }
    }
 
    int tmp = 0;
    while ((tmp = componentNumber()) < 2) {
        if (tmp == 0) {
            ans = 0;
            break;
        }
        ++ans;
        visited = new boolean[301][301];
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] > 0) {
                    temp[i][j] = nextYear(i, j);
                }
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] -= temp[i][j];
            }
        }
    }
    System.out.println(ans);
}
 
public static int componentNumber() {
    int component = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && map[i][j] > 0) {
                ++component;
                dfs(i, j);
            }
        }
    }
    return component;
}
 
public static void dfs(int y, int x) {
    visited[y][x] = true;
 
    for (int i = 0; i < 4; i++) {
        int nx = dx[i] + x;
        int ny = dy[i] + y;
 
        if (0 <= ny && ny < n && 0 <= nx && nx < m) {
            if (!visited[ny][nx] && map[ny][nx] > 0) {
                dfs(ny, nx);
            }
        }
    }
}
 
public static int nextYear(int y, int x) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int nx = dx[i] + x;
        int ny = dy[i] + y;
 
        if (0 <= ny && ny < n && 0 <= nx && nx < m) {
            if (map[ny][nx] <= 0 && map[y][x] > 0) {
                ++cnt;
            }
        }
    }
    return cnt;
}