본문 바로가기

Programming/BOJ

BOJ 2573 · 빙산


알고리즘 분류 : DFS, BFS  


1년마다 빙산이 녹는데, 빙산이 두 덩어리 이상으로 나눠지는 최초 연도를 구하는 문제다. 0은 바다고, 1 이상의 숫자는 빙산의 높이다. 빙산은 인접한 바다의 수(상하좌우)만큼 녹는다. 예를 들어 빙산의 위쪽과 왼쪽이 바다라면, 1년에 2만큼 녹는다.


  • 입력받을 때 바다를 0대신 -1로 저장하고, 빙산의 위치는 Queue에 집어넣는다.
  • 빙산이 녹는 것은 BFS와 비슷한 방법으로, 빙산에 인접한 상하좌우를 확인한다.
  • 만약 인접한 곳이 바다라면, 인접한 수만큼 빙산을 녹인다.
  • 빙산의 개수만큼 모두 녹이고, 연도를 1년 증가시킨다.
  • DFS(또는 BFS)를 통해 두 덩어리 이상으로 쪼개져있는지 확인한다. 2개 이상이라면 연도를 반환하고 종료한다.
  • 두 덩어리 이상이 될 때까지 계속 빙산을 녹이고, 빙산이 모두 녹을 때까지 두 덩어리가 안되면 0을 반환하고 종료한다.




C++ 소스코드


#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct ice {
    int x, y;
};

int n, m;
int a[301][301];
bool check[301][301];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue<ice> q;

void dfs(int x, int y) {
    check[x][y] = true;
    for (int i=0; i<4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (check[nx][ny] || a[nx][ny] < 0) continue;
        dfs(nx, ny);
    }
}

bool counting() {
    int cnt = 0;
    memset(check, false, sizeof(check));
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (!check[i][j] && a[i][j] > 0) {
                dfs(i, j);
                cnt++;
                if (cnt >= 2) return true;
            }
        }
    }
    return false;
}

void melting() {
    queue<ice> p;
    int len = q.size();
    for (int i=0; i<len; i++) {
        int x = q.front().x, y = q.front().y;
        q.pop();
        for (int k=0; k<4; k++) {
            int nx = x+dx[k], ny = y+dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (a[x][y] > 0 && a[nx][ny] == -1) a[x][y] -= 1;
        }
        if (a[x][y] > 0) q.push({x, y});
        else if (a[x][y] == 0) p.push({x, y});
    }
    while (!p.empty()) {
        int x = p.front().x, y = p.front().y;
        p.pop();
        a[x][y] = -1;
    }
}

int solve() {
    int year = 0;
    while (!q.empty()) {
        melting();
        year++;
        if (counting()) return year;
    }
    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j]) q.push({i, j});
            else a[i][j] = -1;
        }
    }
    printf("%d\n", solve());
    return 0;
}




PyPy3 소스코드


from collections import deque
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
q = deque()
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

for i in range(n):
    for j in range(m):
        if a[i][j] > 0:
            q.append((i, j))
        else:
            a[i][j] = -1

def bfs(i, j, check):
    bq = deque()
    bq.append((i, j))
    check[i][j] = True
    while bq:
        x, y = bq.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if check[nx][ny] is False and a[nx][ny] > 0:
                bq.append((nx, ny))
                check[nx][ny] = True

def counting():
    cnt = 0
    check = [[False]*m for _ in range(n)]
    for _ in range(len(q)):
        x, y = q.popleft()
        q.append((x, y))
        if check[x][y] is False:
            bfs(x, y, check)
            cnt += 1
            if cnt >= 2:
                return True
    return False

def melting():
    p = deque()
    for _ in range(len(q)):
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if a[x][y] > 0 and a[nx][ny] == -1:
                a[x][y] -= 1
        if a[x][y] > 0:
            q.append((x, y))
        elif a[x][y] == 0:
            p.append((x, y))
    while p:
        x, y = p.popleft()
        a[x][y] = -1

def solve():
    year = 0
    while q:
        melting()
        year += 1
        if counting() is True:
            return year
    return 0

print(solve())


✓ Python 3로 제출하면 시간 초과가 나오므로, PyPy3로 제출해야 한다.

✓ C++과 달리 counting 함수 구현 방식을 약간 수정했다. DFS대신 BFS를 사용했고, N*M for문 대신 Queue를 사용했다.




참고


태그