백준 - 빙산 (2573)

문제 링크 ▶︎ 백준 빙산 2573

문제 전략

이 문제는 DFS 로 풀고싶어서 DFS 로 풀어본 문제이다.

빙산이 있는 좌표를 ice 라는 딕셔너리에 (키-좌표 밸류-1)로 저장해놓는다.
ice 딕셔너리를 돌면서 dfs 함수를 수행한다.

dfs 는 스택을 통해 구현했다.
스택에서 pop 한 좌표를 상하좌우 탐색하며 바다라면 빙산 값을 줄여주고, 다음 빙산은 stack 에 넣어준다.
만약 빙산이 다 녹아서 0 이하가 된다면 아까 만들어 둔 ice 딕셔너리에서 빼준다.

ice 딕셔너리에 빙산이 존재한다면 while 문을 도는데,
빙산 덩어리가 2개라면 dfs 함수를 2번 돌기 때문에 dfs 돌고 나서는 ices += 1 해준다.

만약에 dfs 함수를 1번만 돌았다면 빙산 덩어리는 1개라는 의미이므로 y += 1 해주고 continue 해준다.

코드

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

ice = {}
for i in range(1,n-1):
    for j in range(1,m-1):
        if maps[i][j]:
            ice[(i,j)] = 1

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


def dfs(y, x):
    stack = [(y, x)]

    while stack:
        y, x = stack.pop()
        if not visit[y][x]:
            visit[y][x] = True
        
            cnt = 0

            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if not visit[ny][nx]:
                    if maps[ny][nx] <= 0:
                        cnt += 1
                    else:
                        stack.append((ny, nx))

            maps[y][x] -= cnt
            if maps[y][x] <= 0:
                ice[(y,x)] = 0

y = 0
while sum(ice.values()) > 0:
    ices = 1 # 처음 빙산 덩어리는 무조건 1개
    visit = [[False] * m for _ in range(n)]

    for k,v in ice.items():
        if v and not visit[k[0]][k[1]]:
            if ices == 2: # 빙산 2개면 출력
                print(y)
                break
            dfs(k[0],k[1]) # 여기에서 모든 ice.items()가 진행되면 아직 빙산 덩어리가 1개 / dfs 함수 1번이 빙산 1덩어리
            ices += 1
    else: # 빙산 덩어리가 2개가 아니면
        y += 1
        continue
    break 

else:
    print(0)

개선 사항

빙산이 다 녹는 year를 구하라는 문제인줄 알았음 -> 문제 잘읽기
사실 다시 풀라해도 다시 못풀거같음.