[파이썬/Python] 백준 2638번: 치즈

숨·2025년 1월 19일

코테

알고리즘 문제 풀이

목록 보기

104/105

📌 문제 : 백준 2638번

📌 문제 탐색하기

N : 세로 격자의 수 ( $5 ≤ N ≤ 100$ )
M : 가로 격자의 수 ( $5 ≤ M ≤ 100$ )

문제 풀이

N×M의 모눈종이 위에 아주 얇은 치즈 위치를 입력받아 이 치즈들이 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 출력하는 문제이다.

⌨️ 치즈가 녹는 규칙

4변 중 2변 이상이 외부와 접촉된 칸

1시간 후에 사라짐

치즈 내부 공간은 공기 접촉 ❌

모눈종이 위 치즈 위치

1 : 치즈 ⭕️

2 : 치즈 ❌

전체 모눈종이를 탐색하면서 치즈가 있는 경우를 찾아 4변 중 2변 이상 0으로 둘러싸여있는지 확인한다.

→ BFS를 활용한다!!

BFS

4가지 방향 탐색
- 범위 내이면서 방문하지 않은 칸 확인
2가지 경우 고려
- 치즈가 없는 칸
  - 방문 처리
  - bfs 이어가기
- 치즈가 있는 칸
  - 딕셔너리에 해당 칸의 공기 접한 변수 저장하기 위해 추가
  - 이미 추가된 상태라면 접한 변 횟수 증가
나중에 bfs를 녹일 치즈가 아예 없는 경우까지 동작
- 딕셔너리에 접근해 변수가 2변 이상인 경우 치즈를 녹였다는 의미로 모눈종이 칸의 값을 0으로 변경
- 시간 추가해준 후 해당 과정을 반복

가능한 시간복잡도

bfs 수행 → $O(N*M)$
치즈 녹이는 최대 시간 → $O(t)$

최종 시간복잡도
$O(t*N*M)$ 으로 최악의 경우 $O(t * 100^2)이 되어 1초 내에 수행할 수 있을 것이다.

알고리즘 선택

치즈가 없을 때까지 bfs 반복

📌 코드 설계하기

bfs 수행
N, M 입력
치즈 정보 입력
4면 접근 방향
시간 초기화
치즈가 다 없어질 때까지 bfs 반복

📌 시도 회차 수정 사항

1회차

처음엔 단순히 치즈가 있는 곳을 찾아 주변에 0이 몇 개인지 세면서 녹는 칸을 구하는 식으로 코드를 작성했는데 원하는 답이 나오지 않았다,
문제에서 치즈 외부, 내부를 구분하도록 되어있는데 무조건 치즈 위치만 찾아서 그런 것 같다. 외부인지 내부인지 고려하는 코드를 추가해야 했다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# bfs 수행
def bfs():
    # 큐 정의
    queue = deque([(0, 0)])
    # 방문 처리
    visited[0][0] = 1
    # 치즈 주변 공기 접촉 횟수 저장할 딕셔너리 정의
    air = {}

    while queue:
        x, y = queue.popleft()

        # 4가지 방향 확인
        for i in range(4):
            nx, ny = x + directions[i][0], y + directions[i][1]

            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                # 치즈가 아닌 경우 찾기
                if board[nx][ny] == 0:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
                # 치즈인 경우 공기 접촉면 세기
                else:
                    if (nx, ny) not in air:
                        air[(nx, ny)] = 1
                    else:
                        # 횟수 추가
                        air[(nx, ny)] += 1
    return air


# N, M 입력
N, M = map(int, input().split())

# 치즈 정보 입력
board = [list(map(int, input().split())) for _ in range(N)]

# 4면 접근 방향
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# 시간 초기화
t = 0

# 치즈가 다 없어질 때까지 bfs 반복
while True:
    # 방문 리스트 정의
    visited = [[0] * M for _ in range(N)]
    air = bfs()

    if not air:  # 녹을 치즈가 없으면 종료
        break

    # 치즈 녹이기
    for (x, y), count in air.items():
        if count >= 2:
            board[x][y] = 0

    # 시간 추가
    t += 1

# 결과 출력
print(t)