[Python/파이썬] 백준 2573번: 빙산

문제

 

풀이

DFS문제, 다만 조금 까다롭게 구현해야 한다.

"만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다." 해당 조건을 구현하지 않아 62%에서 틀렸습니다가 나왔다.

 

[반례]

5 5
0 0 0 0 0
0 2 2 2 0
0 2 2 2 0
0 2 2 2 0
0 0 0 0 0

답 : 0

틀린 답 : 3

 

또한 DFS로 풀 경우

sys.setrecursionlimit(10**4)

setreucrsionlimit에 너무 큰 값을 넣으면 메모리 초과가 나온다. 주의할 것!!

 

코드

import sys
sys.setrecursionlimit(10**4)
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

dir = ((0, 1), (0, -1), (1, 0), (-1, 0))

def check(i, j):
    return i < 0 or i >= n or j < 0 or j >= m

def searchZero(i, j):
    cnt = 0
    for dy, dx in dir:
        ni, nj = dy + i, dx + j
        if check(ni, nj) or graph[ni][nj] != 0: continue
        cnt += 1
    return cnt
    
#빙산 녹음
def melt():
    meltStk = []
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0:
                meltStk.append((i, j, searchZero(i, j)))
    
    for i, j, delIce in meltStk:
        graph[i][j] -= delIce
        if graph[i][j] < 0:
            graph[i][j] = 0
            
#연결된 빙산 파악
def dfs(i, j):
    visited[i][j] = True
    for dy, dx in dir:
        ni, nj = dy + i, dx + j
        if check(ni, nj) or visited[ni][nj] or not graph[ni][nj]: continue
        dfs(ni, nj)

cnt = 0
while True:
    visited = [[False] * m for _ in range(n)]
    ice = 0
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and graph[i][j]:
                dfs(i, j)
                ice += 1
    if ice == 1:    
        melt() 
        cnt += 1
        continue
    if ice == 0:
        print(0)
        break
    print(cnt)
    break

 

마무리

dfs는 역시 시간이 오래 걸리는 것 같다.