치즈 (2638번) - 백준 (BOJ)

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

2638번: 치즈

 

 

백준 - 치즈 (2638번)

 

난이도 : Gold 3

알고리즘 : Simulation & Implementation (구현), BFS or DFS

 

 

import sys
input = sys.stdin.readline


def adjs_conds(r, c):
    if 0 < r:  yield r-1, c
    if r < N-1:  yield r+1, c
    if 0 < c:  yield r, c-1
    if c < M-1:  yield r, c+1
        

def adjs(r, c):
    yield r-1, c
    yield r+1, c
    yield r, c+1
    yield r, c-1


def update_board(cands):
    while cands:
        r, c = cands.pop()
        for rr, cc in adjs(r, c):
            if board[rr][cc]:
                continue
            board[rr][cc] = 2
            cands.append((rr, cc))

            
def find_chz_melts():
    cands = []
    for r in range(N):
        for c in range(M):
            if board[r][c] != 1:
                continue
            if 2 <= sum(1 for rr, cc in adjs(r, c) if board[rr][cc] == 2):
                cands.append((r, c))
    for r, c in cands:
        board[r][c] = 2
    return cands


if __name__ == '__main__':
    N, M = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    board[0][0] = 2
    cands = [(0, 0)]
    while cands:
        r, c = cands.pop()
        for rr, cc in adjs_conds(r, c):
            if board[rr][cc]:
                continue
            board[rr][cc] = 2
            cands.append((rr, cc))
    
    cnt = 0
    while True:
        cands = find_chz_melts()
        if cands:
            cnt += 1
        else:
            break
        update_board(cands)
    print(cnt)

 

 

전형적인 구현 문제이다.

 

외부 공기와 내부 공기를 구분하는 것이 핵심이다.

 

dfs를 활용해서 (bfs도 상관 없다.)

외부 공기는 2로, 내부 공기는 0으로 표시해주었다.

 

①. find_chz_melts 함수를 통해

치즈 1의 상하좌우 중,

외부 공기 2가 2개 이상이라면 녹는 것으로 구현했다.

 

②. 그리고 녹는 치즈가 생기면,

기존의 내부 공기 0이 새로운 외부 공기 2가 될 수 있기 때문에

update_board 함수로 이 부분을 구현했다.

 

위의 ①과 ② 과정을 모든 치즈가 녹을 때까지 반복하면서,

반복 횟수를 세고 반환한다.