[백준] 2638. 치즈 - python

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

2638번: 치즈

문제풀이

• 공기와 2변 이상 접촉한 치즈가 사라지는데 치즈가 모두 녹는데 걸리는 시간 구하는 문제
  • 탐색 (bfs) 문제
  • 공기 접촉면이 2인 구역을 찾아야함 : find 함수로 구현
  • 찾은 치즈를 녹이고 녹인 치즈 갯수 알아냄 : melt 함수로 구현
  • find함수와 melt 함수를 반복해서 실행하고 녹인 치즈가 0개이면 종료하고 그 때 시간을 알아냄
• find 함수
  • 0,0 좌표에서 부터 bfs 탐색을 수행함.
  • 현 좌표에서 상하좌우에 인접한 좌표를 탐색해 나감.
    • 모눈종이를 벗어나면 탐색 중지
    • 치즈를 발견하면 (1이라면) 2로 표시해서 한번 발견됨을 표시
    • 치즈를 발견하는데 이미 한번 발견되었던(즉, 1변을 찾은/ 2라고 표시된) 치즈라면 3으로 표시해서 녹일 치즈임을 나타냄
    • 모눈종이라면 (0이라면) 방문표시 하고(나는 5로 표시) 다른 치즈를 탐색하기 위해서 큐에 좌표 담음
• melt 함수
  • 맵을 순회하면서 3으로 표시된 갯수세기
  • 다음 find함수 실행을 위해서 상태 변경해주기
    • 5 ( 방문한 모눈종이) -> 0
    • 2 (한변만 공기접촉한 치즈) -> 1
    • 3 (2변이상 공기접촉한 치즈) -> 0 (녹아 없어지므로)

소스코드 - python

dr = [-1,0,1,0]
dc = [0,1,0,-1]
def find(r,c):
    q = []
    q.append([r,c])
    m[r][c] = 5
    while q:
        cur = q.pop(0)
        for k in range(4):
            nr = cur[0] + dr[k]
            nc = cur[1] + dc[k]
            if nr < 0 or nr >= N or nc < 0 or nc >=M : continue
            if m[nr][nc] == 5 : continue
            elif m[nr][nc] == 1 : m[nr][nc] = 2
            elif m[nr][nc] == 2 : m[nr][nc] = 3
            elif m[nr][nc] == 0 :
                m[nr][nc] = 5
                q.append([nr,nc])

def melt():
    cnt = 0
    for i in range(N):
        for j in range(M):
            if m[i][j] == 5 : m[i][j] = 0
            if m[i][j] == 2 : m[i][j] = 1
            if m[i][j] == 3 :
                cnt += 1
                m[i][j] = 0
    return cnt

N,M = map(int,input().split())
m = [ list(map(int,input().split())) for _ in range(N)]
time = 0
m_cnt = 0
while True:
    find(0,0)
    m_cnt = melt()
    if m_cnt == 0 : break
    time += 1
print(time)