Baekjoon 2638. 치즈 / Python

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

문제 요약

N×M의 격자판에 치즈가 놓여 있다. 치즈의 각 격자(작은 정사각형 모양)는 4변 중 2변 이상이 공기와 접촉하면 한 시간 만에 녹아 없어지게 된다. 이때 치즈가 모두 녹아 없어지는 데 걸리는 시간을 구하는 문제다.

알고리즘 및 코드 설명

알고리즘

1. 치즈 외부 공기 탐색: BFS를 사용하여 외부 공기를 탐색하고, 외부 공기와 접촉한 치즈를 표시한다.
2. 치즈 녹이기: 외부 공기와 2변 이상 접촉한 치즈를 녹인다.
3. 반복: 치즈가 모두 녹을 때까지 1~2의 과정을 반복한다.
4. 시간 측정: 치즈가 모두 녹을 때까지 걸린 시간을 측정하여 출력한다.

시간복잡도

• BFS 탐색은 O(N×M) 시간 복잡도를 가진다.
• 치즈를 녹이는 과정도 O(N×M)이다.
• 최악의 경우, 치즈가 녹는 과정을 여러 번 반복해야 하므로 전체 시간 복잡도는 O(T×N×M)이다. 여기서 T는 치즈가 완전히 녹을 때까지 걸리는 시간의 단위이다.

코드 설명

1. 입력 처리: 격자의 크기 nnn, mmm과 치즈 배열을 입력받는다.
2. 방향 벡터 설정: 상하좌우 방향을 나타내는 벡터를 설정한다.
3. bfs1 함수: BFS를 사용하여 외부 공기를 탐색하고, 외부 공기와 접촉한 치즈를 표시한다.
4. bfs2 함수: 외부 공기와 2변 이상 접촉한 치즈를 녹인다. 녹은 치즈의 수를 반환한다.
5. 메인 루프: bfs1과 bfs2를 반복하여 치즈가 모두 녹을 때까지 진행한다. 치즈가 모두 녹으면 최종 시간을 출력하고 종료한다.

import sys
from collections import deque as dq

input = sys.stdin.readline

n, m = map(int, input().split())  # 격자의 크기 n, m
cheese = [list(map(int, input().split())) for _ in range(n)]  # 치즈 배열 입력
direction = [(1, 0), (0, 1), (0, -1), (-1, 0)]  # 상하좌우 방향 벡터

# 외부 공기를 BFS로 탐색하여 외부 공기와 접촉한 치즈를 표시하는 함수
def bfs1():
    visit = [[0] * m for _ in range(n)]  # 방문 여부 배열
    q = dq([(0, 0)])  # 시작점은 (0, 0)
    visit[0][0] = 1  # 시작점 방문 처리
    while q:
        x, y = q.popleft()
        for dx, dy in direction:  # 네 방향에 대해 탐색
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:  # 격자 범위 내에 있는지 확인
                if not visit[nx][ny]:  # 방문하지 않은 곳이라면
                    if not cheese[nx][ny]:  # 치즈가 없는 곳이라면
                        visit[nx][ny] = 1   
                        q.append((nx, ny))  # 큐에 추가하여 BFS 진행
                    else:
                        cheese[nx][ny] += 1  # 치즈가 있는 곳이라면 접촉 횟수 증가

# 치즈를 녹이는 함수
def bfs2():
    melt_cnt = 0  # 녹은 치즈의 수
    for i in range(n):
        for j in range(m):
            if cheese[i][j] >= 3:  # 2변 이상 공기와 접촉한 치즈는 녹음
                cheese[i][j] = 0
                melt_cnt += 1  # 녹은 치즈 개수 증가
            elif cheese[i][j] == 2:  # 공기와 한 변만 접촉한 치즈는 다시 초기화
                cheese[i][j] = 1
    return melt_cnt  # 녹은 치즈 개수 반환

time = 0  # 시간을 측정할 변수
while True:
    bfs1()  # 외부 공기 탐색 및 표시
    tmp_cnt = bfs2()  # 치즈 녹이기
    if tmp_cnt:  # 녹은 치즈가 있다면
        time += 1  # 시간 증가
    else:  # 녹은 치즈가 없다면
        print(time)  # 최종 시간 출력
        break  # 루프 종료