[백준 #2573 파이썬] 빙산

빙산 문제도 연구소와 어느정도 비슷한 점이 많다고 생각했다. 

 

생각해야 하는 부분들

 

1. 얼음이 모두 녹는 경우 음수가 되어서는 안된다.

2. 녹아서 물이 된 경우,그 결과는 바로 반영되는 것이 아닌 내년에 반영된다.

3. 두동강이 나면 끝난다.

4. 아예 녹으면 끝난다.

 

예전에 구름 알고리즘 챌린지에서 비슷한 문제를 풀어본 경험이 있다 (단풍나무 문제 링크가 있으면 추가해드릴게요!)

여기에서 1, 2번 문제를 해결했던 경험이 있어 이를 활용하고자 했다

 

구현

1 해결 : max 활용

어쩌면 dp를 하면서 가장 많이 봤을 키워드였다. 하나의 빙산의 숫자가 2이고 3면이 바다인 상황을 가정해보자.

그러면 bfs를 돌리면 -1이라는 값이 된다. 하지만 max(0,현재 빙산 숫자 -  접하는 면의 바다)라는 로직을 통해 0으로 만들어줄 수 있다. 

 

2 해결 : 모든 bfs가 돌린 다음에 처리

우선 바다를 만나는 빙하는 모두 값에 변화가 있을 것이다. 하지만 이는 바로 반영되어서는 안되기 때문에 리스트에 따로 담아둔다. 그리고 큐가 끝날 경우 마지막에 저장된 값 바다 면 만큼 값을 빼는 해결 1 을 시행하면 됩다.

 

3 4 해결 : 두동강이 나면 끝난다.

 

 

 

 

사실 이 옵션에 대해서 고민이 많았다. bfs 내에서 처리를 해줘야 하는 건지 밖에서 따로 로직을 만들어서 처리해야 하는 지 몰라 답을 참고했다. 근데 생각보다는 간단하게 처리할 수 있었다. bfs의 리턴 값을 1로 주고 이를 카운트하는 방식으로 처리를 하면 된다. bfs가 한번 돌면 한 덩어리의 빙산이 있는 것이고 다시 한 번 돌면 한 덩어리의 빙산이 다시 있다는 것을 의미한다. 어쩌면 bfs의 특성이라는 생각도 든다. 

 

놓친 문제

이제 구현한 함수를 실제로 탐색하는 방향에서 어려움이 있어 답을 참고했다.

이 부분에서는 현재 빙산인 곳과 빙산이 아닌 곳을 bfs에서 해주듯 따로 리스트로 저장해두고 while문을 돌리고 이 리스트를 소거해나가는 방식으로 구현해볼 수 있었다! 

 

여기서 배운 점은 리스트를 따로 만들어서 값을 저장해두고 활용하는 방식, 그리고 dp처럼 생각해볼 수 있는 값처리가 있었다!

 

얼른 bfs 마스터하고 싶다...ㅎ

from collections import deque

n,m = map(int,input().split())
ground = [list(map(int,input().split())) for i in range(n)]
dx= [0,0,-1,1]
dy= [1,-1,0,0]
year = 0 

def bfs(a,b):
    q = deque()
    q.append([a,b])
    visited[a][b] = 1
    chk = []
    while q:
        sea = 0
        x,y = q.popleft()
        for i in range(4):
            nx,ny = dx[i]+x,dy[i]+y
            if 0<=nx<n and 0<=ny<m:
                if not ground[nx][ny]:
                    sea += 1
                elif ground[nx][ny] and not visited[nx][ny]:
                    q.append([nx,ny])
                    visited[nx][ny] = 1
        chk.append([x,y,sea])
    for i,j,sea in chk:
        ground[i][j] = max(0,ground[i][j] - sea)
    return 1

ice = []
for i in range(n):
    for j in range(m):
        if ground[i][j]:
            ice.append((i,j))
    
while ice:
    visited = [[0]*m for _ in range(n)]
    dellist = []
    group = 0
    for i,j in ice:
        if ground[i][j] and not visited[i][j]:
            group += bfs(i,j)
        if ground[i][j] == 0:
            dellist.append((i,j))
    if group > 1:
        print(year)
        break
    ice =sorted(list(set(ice) - set(dellist)))
    year += 1

if group < 2:
    print(0)