[221003] 백준 2573 : 빙산

https://www.acmicpc.net/problem/2573

2573번: 빙산

1. 빙산 덩어리 개수 세는 것과 녹이는 것을 동시에 진행해야 함.

 큐의 사용을 최소화 해야한다. 빙산 덩어리를 세면서 녹여야 한다. 한 덩어리 세고, 녹이고, 그 다음 덩어리 구간 파악하고, 녹이고, 이런식으로 진행해야한다. 큐를 사용하는 경우를 늘리면 바로 시간초과가 나버린다.

2. 전체 코드

메모리 : 164096 KB, 시간 : 564 ms, 풀이 시간 : 40 min

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

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

def bfs(x, y, visited) :
    q = [[x, y]]
    melt_q = []
    visited[x][y] = True
    while q :
        x, y = q[0]
        del q[0]
        melt_cnt = 0
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]
            if (0 <= nx < N) and (0 <= ny < M) and not visited[nx][ny] :
                if board[nx][ny] != 0 :
                    visited[nx][ny] = True
                    q.append([nx, ny])
                else :
                    melt_cnt += 1
        if melt_cnt :
            melt_q.append([x, y, melt_cnt])
    return melt_q

year = 0
while True :
    count = 0
    visited = [[False for _ in range(M)] for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if board[i][j] != 0 and not visited[i][j] :
                count += 1
                # 처음부터 덩어리를 세고 시작함
                melt = bfs(i, j, visited)
                while melt :
                    mx, my, m = melt[0]
                    del melt[0]
                    board[mx][my] = max(board[mx][my] - m, 0)
    # visited 함수가 방문처리를 할테니 덩어리 마다 계산 수행이 끝나면
    # 종료 조건 확인 후 1년 추가
    if count == 0 :
        year = 0
        break
    if count >= 2 :
        break
    year += 1
print(year)