백준 2573 빙산

haruponea·2021년 3월 24일
0

BOJ

목록 보기
23/41

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

풀이
풀이 방법에 따라서 시간초과가 날 수 있는 문제였습니다. 키포인트는 bfs를 돌면서 인접칸의 얼음 수를 세야한다는 점입니다. bfs를 돌고나서 전체 board를 또 돌면서 얼음칸을 세면 시간초과가 날 수 있음에 유의합시다! bfs를 돌면서 defaultdict에 현재 칸을 key로 주변 얼음의 수를 value로 저장했습니다

Python

from collections import deque, defaultdict
import sys
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
>
n, m = map(int, sys.stdin.readline().split())
board1 = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
t = 0
>
>
def bfs(x, y, vis):
    vis[x][y] = True
    q = deque()
    q.append((x, y))
    land = defaultdict(int)
    while q:
        curx, cury = q.popleft()
        for i in range(4):
            nx = curx + dx[i]
            ny = cury + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if vis[nx][ny] == False and board1[nx][ny] != 0:
                    vis[nx][ny] = True
                    q.append((nx, ny))
                if board1[nx][ny] == 0:
                    land[(curx, cury)] += 1
    return land
>
>
while True:
    vis = [[False] * m for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(m):
            if board1[i][j] != 0 and vis[i][j] == False:
                cnt += 1
                ice = bfs(i, j, vis)
    if cnt == 0:
        print(0)
        break
    elif cnt == 1:
        t += 1
        for (x, y), ice_cnt in ice.items():
            board1[x][y] = board1[x][y] - ice_cnt if board1[x][y] - ice_cnt > 0 else 0
        continue
    else:
        print(t)
        break

0개의 댓글