[백준/Python] 2573. 빙산

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

📌  문제 접근

빙산은 1년 동안 동서남북 방향으로 접한 바닷물 칸수만큼 줄어든다.

빙산이 두 덩어리가 됐을 때가 몇 년 후 인지 구하는 문제이다. 단 두 덩어리가 되지 못하면 0을 출력해야 한다.

문제를 읽으며 dfs나 bfs로 풀면 되겠다고 생각했다. 

 

🧐 첫 번째 풀이: DFS (실패)

처음에는 DFS로 연결된 빙산을 탐색했다.

def dfs(x, y):
    visited[x][y] = 1
    for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] != 0 and visited[nx][ny] == 0:
            dfs(nx, ny)


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

year = 0
while True:
    visited = [[0] * M for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(M):
            if arr[i][j] != 0 and visited[i][j] == 0:
                dfs(i, j)
                cnt += 1

    if cnt >= 2:
        break

    if cnt == 0:
        year = 0
        break

    melt = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if arr[i][j] != 0:
                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0:
                        melt[i][j] += 1

    for i in range(N):
        for j in range(M):
            arr[i][j] = max(0, arr[i][j] - melt[i][j])

    year += 1

print(year)

 

하지만 RecursionError가 발생했다.

sys.setrecursionlimit()으로 제한을 늘릴 수도 있지만 효율적인 탐색을 위해 BFS로 다시 풀었다.

 

🧐 두 번째 풀이: BFS (실패)

이번에는 시간초과가 발생했다.

from collections import deque

def bfs(x, y):
    q = deque([(x, y)])
    visited[x][y] = 1

    while q:
        cx, cy = q.popleft()
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] != 0 and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx, ny))


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

year = 0
while True:
    visited = [[0] * M for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(M):
            if arr[i][j] != 0 and visited[i][j] == 0:
                bfs(i, j)
                cnt += 1

    if cnt >= 2:
        break

    if cnt == 0:
        year = 0
        break

    melt = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if arr[i][j] != 0:
                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0:
                        melt[i][j] += 1

    for i in range(N):
        for j in range(M):
            arr[i][j] = max(0, arr[i][j] - melt[i][j])

    year += 1

print(year)

 

아무래도 while문 안에 빙산 탐색을 위한 for문, 바닷물을 저장할 for문, 빙산을 녹이는 for문이 모두 있어서 생기는 것 같았다.

 

😃 세 번째 풀이: BFS (성공)

이번에는 BFS를 탐색하면서 주변 바닷물의 수를 저장하고 탐색이 끝나면 저장한 좌표만 녹이는 방식으로 바꾸었다.

from collections import deque

def bfs(x, y):
    q = deque([(x, y)])
    visited[x][y] = 1
    melt = []

    while q:
        cx, cy = q.popleft()
        sea = 0
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] == 0:
                    sea += 1
                elif arr[nx][ny] != 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
        if sea > 0:
            melt.append((cx, cy, sea))

    for cx, cy, sea in melt:
        arr[cx][cy] = max(0, arr[cx][cy] - sea)

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

year = 0
while True:
    visited = [[0] * M for _ in range(N)]
    cnt = 0

    for i in range(N):
        for j in range(M):
            if arr[i][j] != 0 and visited[i][j] == 0:
                bfs(i, j)
                cnt += 1

    if cnt >= 2:
        print(year)
        break

    if cnt == 0:
        print(0)
        break

    year += 1

 

배열 전체를 여러 번 돌지 않고 빙산이 있는 칸만 처리하게 되어 훨씬 효율적이었다.