백준 2573 (빙산)

백준 2573 (빙산)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/2573

문제 접근

반갑습니다. 오늘은 오랜만에 그래프 탐색 문제를 가져왔습니다. 지구 온난화가 심각한 듯 합니다.. 문제에서까지 지구 온난화를 주제로 한 문제가 나오다니 후덜덜하네요. 각설하고, 빙산은 바다에 의해 녹는다는 자명한 사실을 머릿속에 깔고 갑시다. 북극을 격자점으로 형상화했습니다. 0은 바다, 나머지 숫자는 빙하라고 합니다. 빙하의 인접한 바다의 수에 하나당, 빙하가 하나씩 녹는다고 합니다. 빙산이 두 덩어리로 분리될 때의 시간을 출력하는 문제입니다. 물론 문제에서, 처음의 빙하는 무조건 한 덩어리로 주어집니다.

크게 어렵지 않은 문제입니다. 격자점의 사이즈가 얼마 되지 않고, 빙하의 갯수가 최대 10000개가 되지 않기에, 탐색 한 번에 소요되는 빙하의 수는 10000을 넘지 않습니다. 따라서, 간단하게 문제의 흐름에 몸을 맡기고 구현하면 되는 문제입니다.

설명을 좀 하자면, 빙하가 있는 지점에서의 인접한 바다의 수를 구하고, 이를 고려해 빙하를 녹입니다. 빙하를 녹이고 덩어리가 두 개 이상 된다면 그냥 걸린 시간을 출력하면 됩니다. 근데 edge case가 있습니다. 빙산이 다 녹을 때, 분리되지 않는다면, 즉 덩어리가 2개 이상 생기는 케이스가 없다면 0을 출력해야 합니다.

0 0 0 1 1 0

같은 케이스로 주어진다면 한 번에 빙하가 다 녹아버리기에, 0을 출력해야 한다는 것입니다. 이를 고려해서 구현해봅시다. 빙하 덩어리의 수를 chunk로 선언했습니다. 빙하를 녹이고, BFS 방식으로 빙하 덩어리의 수를 구했습니다. 먼저 빙하를 녹이기에, 검사 시 만약 빙하가 없다는 것은, 한 번에 다 녹아버려 덩어리가 생기지 않았다는 의미입니다.

소스 코드

import sys
from collections import deque

n,m=map(int, sys.stdin.readline().split())
graph=[list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
answer=0

while True : 
    answer+=1
    count=[[0 for _ in range(m)] for _ in range(n)] 
    for row in range(n) : #인접한 바다의 수 구하기, count 배열에 저장했습니다.
        for col in range(m) :
            if graph[row][col]!=0:
                zero=0
                for i in range(4) :
                    next_x=row+dx[i]
                    next_y=col+dy[i]
                    if (next_x>=0 and next_x<n) and (next_y>=0 and next_y<m) :
                        if graph[next_x][next_y]==0 :
                            zero+=1
                count[row][col]=zero
        
    for row in range(n) :
        for col in range(m) :
            if graph[row][col]!=0 :
                graph[row][col]=max(0, graph[row][col]-count[row][col]) # 0보다 작을 순 없습니다. -> 빙하 녹이기
    
    visited=[[False for _ in range(m)] for _ in range(n)]
    #chunk 수 구하기  
    chunk=0      
    for row in range(n) :
        for col in range(m) :         
            if graph[row][col]!=0 and not visited[row][col]: 
                queue=deque()
                queue.append((row,col))
                visited[row][col]=True
                chunk+=1
                while queue : #bfs
                    pos_x, pos_y= queue.popleft()
                    for i in range(4) :
                        next_x=pos_x+dx[i]
                        next_y=pos_y+dy[i]
                        if (next_x>=0 and next_x<n) and (next_y>=0 and next_y<m) : # and visited[next_x][next_y]==(-1)
                            if graph[next_x][next_y]!=0 and not visited[next_x][next_y] :
                                queue.append((next_x, next_y))
                                visited[next_x][next_y]=True
    if chunk==0 :
        print(0)
        break
    elif chunk>=2 :
        print(answer)
        break

마무리하며

순차적으로 구현하여 코드가 조금 깁니다. 간단한 BFS 문제였습니다. 유사 3학년인 4학년의 삶이란 참 바쁜 듯 합니다!!!!