[백준 문제풀이] 얼렁뚱땅 2573 빙산 풀이

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

2573번: 빙산

 

import sys

sys.setrecursionlimit(10**5)

n, m = map(int,sys.stdin.readline().split())
arr = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(n)]

count = 1
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def dfs(x,y) :
    global visited

    visited[x][y] = 1

    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<m and arr[nx][ny]!=0 and visited[nx][ny] == 0 :
            dfs(nx,ny)

while True :
    # 주변 0 개수 체크
    t = []
    for x in range(n) :
        for y in range(m) :
            if arr[x][y] != 0 :
                sign = 0
                for k in range(4) :
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<n and 0<=ny<m and arr[nx][ny] == 0 :
                        sign += 1
                t.append([x,y,max(0,arr[x][y]-sign)])

    while t :
        x,y,q=t.pop()
        arr[x][y] = q

    # 몇 덩어리인지 파악
    visited = [[0]*m for _ in range(n)]
    temp = 0
    for i in range(n) :
        for j in range(m) :
            if arr[i][j] != 0 and visited[i][j] == 0 :
                temp += 1
                if temp >= 2 : 
                    print(count)
                    sys.exit()
                dfs(i,j)

    if temp == 0 :
        print(0)
        sys.exit()
    elif temp < 2 :
        count+=1