[Python] 백준 #2573 - 빙산

문제

---

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

2573번: 빙산

 

 

 

풀이

---

from collections import deque

n,m = map(int,input().split())
arr = []
for i in range(n):
    a = list(map(int,input().split()))
    arr.append(a)


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

def bfs(arr,x,y):
    queue = deque()
    queue.append([x,y])

    while queue:
        x,y = queue.popleft()
        visited[x][y] = True
        for i in range(4):
            node_x = x + dx[i]
            node_y = y + dy[i]
            if 0<= node_x < n and 0<= node_y < m:
                if visited[node_x][node_y] == False and arr[node_x][node_y] != 0:
                    queue.append([node_x,node_y])
                    visited[node_x][node_y] = True
                elif arr[node_x][node_y] == 0:
                    count[x][y] += 1
    return 1


year = 0
check_0 = False
while True:
    visited = [[False for _ in range(m)] for _ in range(n)]
    count = [[0]*m for _ in range(n)]
    result = []

    # 빙산 개수 확인
    for i in range(n):
        for j in range(m):
            if arr[i][j]!=0 and visited[i][j] == False:
                result.append(bfs(arr,i,j))
    if len(result) == 0: # 빙산이 없으면
        check_0 = True 
        break
    elif len(result) >= 2: # 빙산이 2개 이상이면
        break

    # 빙산 녹임
    for i in range(n):
        for j in range(m):
            arr[i][j] -= count[i][j]
            if arr[i][j] < 0 : arr[i][j] = 0
    year+=1

if check_0: print(0)
else: print(year)

 

bfs 를 사용해서 풀었다.

 

빙산의 개수를 bfs로 체크해준다. 이때 count 리스트를 사용하여 주변 0의 개수를 구해준다.

 

만약 빙산이 없으면 0을 출력해주고 빙산이 2개 이상이면 시간을 출력해준다.

 

빙산이 1개면 주변 0의 개수를 구했던 count 리스트를 사용하여 빙산을 녹여준다.

 

정리전 코드 <참고용>

from collections import deque

n,m = map(int,input().split())
arr = []
for i in range(n):
    a = list(map(int,input().split()))
    arr.append(a)


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


def melt(arr):

    tmp = [[0 for i in range(m)] for j in range(n)]

    for i in range(n):
        for j in range(m): 
            cnt=0
            if arr[i][j] !=0:
                for p in range(4):
                    if 0<= i+dx[p] < n and  0<= j+dy[p] < m:
                        if arr[i+dx[p]][j+dy[p]] == 0:
                            cnt+=1
                tmp[i][j] = arr[i][j]-cnt
                if tmp[i][j] < 0: tmp[i][j] = 0
    # print()
    # for i in range(n):
    #     print(*tmp[i])
    return tmp

def bfs(arr,x,y):
    queue = deque([[x,y]])

    while queue:
        q = queue.popleft()
        for i in range(4):
            node_x = q[0] + dx[i]
            node_y = q[1] + dy[i]
            if 0<= node_x < n and 0<= node_y < m:
                if visited[node_x][node_y] == False and arr[node_x][node_y] != 0:
                    queue.append([node_x,node_y])
                    visited[node_x][node_y] = True
# visited = [[False for i in range(m)] for j in range(n)]
# c=0
# for i in range(len(arr)):
#     for j in range(len(arr)):
#         if arr[i][j]!=0 and visited[i][j] == False:
#             bfs(arr,i,j)
#             c+=1
# print(c)



year = 0
sol=False
while True:
    visited = [[False for _ in range(m)] for _ in range(n)]
    cnt=0
    check_0 = False
    for i in range(n):
        for j in range(m):
            if arr[i][j] !=0: check_0 = True
            if arr[i][j]!=0 and visited[i][j] == False:
                if cnt!=0: 
                    sol = True
                    break
                bfs(arr,i,j)
                cnt+=1
        if sol == True: break
    else:
        if check_0 == False : break
        arr = melt(arr)
        year +=1
    if sol == True:
        break
if check_0 == False: print(0)
else: print(year)