💻 문제: 2636 - 치즈
- 문제 링크: https://www.acmicpc.net/problem/2636
- 알고리즘 분류: 너비 우선 탐색(BFS), 시뮬레이션, 그래프 이론
문제 소개 🧐
N×M 모눈종이 위에 치즈가 놓여 있다. 치즈는 실내온도에 노출되면 녹는데, 각 치즈 격자의 4변 중 적어도 2변 이상이 공기와 접촉하면 한 시간 만에 녹아 없어진다. 단, 치즈 내부에 있는 공간은 외부 공기와 접촉하지 않는 것으로 간주한다.
모눈종이의 맨 가장자리에는 치즈가 놓이지 않으며, 치즈가 모두 녹아 없어지는 데 걸리는 시간을 구해야 한다.
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 37332 | 17795 | 13259 | 46.373% |
입력 📝
- 첫째 줄: 모눈종이의 크기 N, M (5 ≤ N, M ≤ 100)
- 둘째 줄부터 N개의 줄: 치즈가 있는 부분은 1, 없는 부분은 0으로 표시된다.
출력 📤
- 치즈가 모두 녹아 없어지는 데 걸리는 시간을 정수로 출력한다.
풀이 1: 단순 탐색과 잘못된 가정 😭
Idea 1
처음에는 간단하게 생각했다. 매 시간마다 모든 치즈 조각을 순회하면서, 각 치즈의 상하좌우를 확인하여 공기(값이 0인 칸)와 몇 번 접촉하는지 세면 되지 않을까? 만약 2번 이상 접촉하면 녹을 치즈 목록에 추가하고, 한 타임의 순회가 끝나면 목록에 있는 치즈들을 한 번에 녹이면(0으로 바꾸면) 될 것이라고 생각했다.
이 과정을 치즈가 모두 사라질 때까지 반복하면 정답을 찾을 수 있을 것이라 가정했다.
Code
import sys
N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 하 우 상 좌
cheeses = set()
for i in range(N):
for j in range(M):
if board[i][j] == 1:
cheeses.add((i,j))
time = 0
while cheeses:
time += 1
# 1. 각 치즈들에 대해 녹을 치즈인지 검사
melting_cheeses = set()
for r, c in cheeses:
cnt = 0
for dr, dc in moves:
nr = r + dr
nc = c + dc
if 0 <= nr < N and 0 <= nc < M and board[nr][nc] == 0:
cnt += 1
if cnt > 1:
melting_cheeses.add((r,c))
# 2. 구해진 녹을 치즈 자리를 0으로 바꿈
for r, c in melting_cheeses:
board[r][c] = 0
# 3. 녹을 치즈를 치즈 셋에서 없앰
cheeses = cheeses.difference(melting_cheeses)
print(time)
Result
- 결과: 실패 😭
- 이 접근은 치즈 안의 구멍(내부 공기)과 외부 공기를 구분하지 못했다. 문제에서는 외부 공기에 닿아야만 녹는다고 했는데, 이 코드는 내부 구멍에 닿아도 녹는 것으로 처리했기 때문에 잘못된 결과를 낳았다.
풀이 2: BFS로 외부 공기 판별하기 💪
Idea 2
첫 번째 시도의 문제점을 해결하기 위해, ‘외부 공기’를 명확하게 정의하고 시작해야 함을 깨달았다. 외부 공기는 항상 (0, 0)과 연결되어 있다. 따라서 매 시간마다 BFS를 (0, 0)에서 시작하여 외부 공기가 닿을 수 있는 모든 칸을 먼저 구별해냈다.
- (0, 0)에서 BFS를 시작하여 외부 공기인 칸들을 모두
True로 표시한is_atmosphere배열을 만든다. - 모든 치즈를 순회하며, 인접한 칸이
is_atmosphere에서True인 경우만 카운트한다. - 이 카운트가 2 이상이면 해당 치즈는 녹을 치즈다.
- 이 과정을 치즈가 모두 사라질 때까지 반복한다.
Code
import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 하 우 상 좌
def bfs(board, cheeses: set):
"""
항상 0,0 에서 BFS를 시작해서 외부 공기 셋을 반환하는 함수
"""
global N, M
q = deque()
q.append((0,0))
visited = [[False for _ in range(M)] for _ in range(N)]
while q:
r, c = q.popleft()
for dr, dc in moves:
nr = r + dr
nc = c + dc
if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc] and board[nr][nc] != 1:
visited[nr][nc] = True
q.append((nr,nc))
return visited
cheeses = set()
for i in range(N):
for j in range(M):
if board[i][j] == 1:
cheeses.add((i,j))
time = 0
while cheeses:
time += 1
# 0. 외부 공기 영역 구함
is_atmosphere = bfs(board, cheeses)
# 1. 각 치즈들에 대해 녹을 치즈인지 검사
melting_cheeses = set()
for r, c in cheeses:
cnt = 0
for dr, dc in moves:
nr = r + dr
nc = c + dc
if 0 <= nr < N and 0 <= nc < M and is_atmosphere[nr][nc]:
cnt += 1
if cnt > 1:
melting_cheeses.add((r,c))
# 2. 구해진 녹을 치즈 자리를 0으로 바꿈
for r, c in melting_cheeses:
board[r][c] = 0
# 3. 녹을 치즈를 치즈 셋에서 없앰
cheeses = cheeses.difference(melting_cheeses)
print(time)
Result
- 결과: 성공! 🎉
- 매 시뮬레이션 턴마다 외부 공기를 새로 정의하고 녹는 치즈를 계산하는 방식으로 문제를 해결할 수 있었다.
배운 점 및 개선할 부분 🤔
- 경계 조건의 명확화: 시뮬레이션 문제에서는 ‘외부’, ‘내부’, ‘경계’와 같은 상태를 명확하게 정의하는 것이 매우 중요하다는 것을 다시 한번 깨달았다. 이 문제에서는 ‘외부 공기’를 어떻게 판별할 것인가가 핵심이었다.
- BFS/DFS의 활용: 격자 형태의 맵에서 특정 영역(외부 공기)을 구분해내는 데에는 BFS나 DFS가 매우 효과적인 도구다. 특히 가장자리에서 탐색을 시작하는 패턴은 이런 종류의 문제에서 자주 사용된다.
- 실패로부터 배우기: 첫 번째 실패가 없었다면 ‘내부 공기’의 존재를 간과했을 것이다. 잘못된 접근을 통해 문제의 핵심 제약 조건을 더 깊이 이해하게 되었다.
시뮬레이션은 상태 정의에서 시작된다. 경계를 명확히 하자!
⁂