[BOJ] Q2573 빙산

[BOJ] Q2573 빙산

Question

Language: Python

Difficulty: Gold 4

이 문제는 bfs을 통해서 components을 구할 수 있는 지 여부를 판단하는 문제의 일종이다. components는 전체 bfs 호출 횟수를 이용해서 구할 수 있다.

그 외 나머지 부분은 문제에 주어진 조건에 따라 구현하면 된다.

빙산을 녹이는 과정에서 해당 칸을 바로 녹이지 않고, 리스트를 이용해서 모은 후에 한번에 녹이는 작업을 수행한다. 미리 녹이게 되면 인접한 빙산에서 인접한 빙칸의 개수를 구하는 과정에서 예상치 못한 빈칸이 생겨, 녹이는 작업이 정상적으로 작동되지 않는 경우가 발생할 수 있다.

Solution

from collections import deque
def components():
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    count=0
    visited=[[False] *n_cols for _ in range(n_rows)]
    
    for row in range(n_rows):
        for col in range(n_cols):
            if graph[row][col] != 0 and not visited[row][col]:
                queue=deque([(row,col)])
                while queue:
                    cur_row,cur_col=queue.popleft()

                    if visited[cur_row][cur_col]:
                        continue
                    
                    visited[cur_row][cur_col]=True
                
                    for dir in range(4):
                        new_row=cur_row+dy[dir]
                        new_col=cur_col+dx[dir]

                        if graph[new_row][new_col] !=0:
                            queue.append((new_row,new_col))
                count+=1

    return count

def solution():
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    time=0
    while True:
        candidates=[]
        for row in range(n_rows):
            for col in range(n_cols):
                if graph[row][col] != 0:
                    count=0
                    for dir in range(4):
                        new_row=row+dy[dir]
                        new_col=col+dx[dir]
                        
                        if graph[new_row][new_col]==0:
                            count+=1
                    candidates.append((row,col,count))
        
        #더 이상 빙산이 안 남아있는 경우
        if len(candidates) == 0:
            return 0

        #빙산에 대해서 녹이는 작업을 수행한다.
        for row,col,count in candidates:
            graph[row][col]-=min(count,graph[row][col])
        time+=1
        
        count=components()
        if count>=2:
            return time
    
if __name__ == "__main__":
    n_rows,n_cols=map(int,input().split())
    graph=[list(map(int,input().split())) for _ in range(n_rows)]
    print(solution())