백준 2638번: 치즈 (골드 3)
문제
N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.
<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.
모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.
출력
출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.
예제 입력 1 복사
8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
예제 출력 1 복사
4
사고(고민) 과정
공기와 접촉한 치즈 격자? 4방향(상하좌우) 중 2번 이상이 0(공기)면 녹음
단, 내부의 0은 공기가 아니고, 외부와 연결된 0만 공기로 간주
매 시간마다 녹는 치즈를 전부 파악 후, 동시에 녹여야 함
외부 공기 탐색은 BFS로 (0,0)에서 시작하여 퍼져나가면 해결
- 외부 공기(0)을 BFS로 구분(visited 사용)
- 치즈(1)을 하나하나 돌며, 인접한 공기 방향이 2개 이상인 칸을 녹이기 대상으로 체크
- 체크한 치즈들을 모두 0으로 바꾸고, 시간이 1 증가
- 모든 치즈가 없어질 때까지 반복
- 걸린 시간 출력
풀이 방법
from collections import deque
import sys
input = sys.stdin.readline
def melt_cheese(board, N, M):
time = 0
def mark_outside_air():
visited = [[False]*M for _ in range(N)]
q = deque()
q.append((0,0))
visited[0][0] = True
while q:
x, y = q.popleft()
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = x+dx, y+dy
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
if board[nx][ny] == 0:
visited[nx][ny] = True
q.append((nx, ny))
elif board[nx][ny] == 1:
visited[nx][ny] = True
return visited
while True:
air = mark_outside_air()
melt = []
for i in range(N):
for j in range(M):
if board[i][j] == 1:
contact = 0
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+dx, j+dy
if air[ni][nj] and board[ni][nj] == 0:
contact += 1
if contact >= 2:
melt.append((i, j))
if not melt:
return time
for i, j in melt:
board[i][j] = 0
time += 1
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
print(melt_cheese(board, N, M))
풀이 시 중점 고려 사항/핵심 문법 정리 등
- N: 세로 길이, M: 가로 길이
- board: 치즈가 있는 모눈종이 (2차원 리스트)
- 0: 공기
- 1: 치즈
외부 공기 탐색 함수: mark_outside_air()
def mark_outside_air():
visited = [[False]*M for _ in range(N)]
q = deque()
q.append((0, 0)) # 외부 공기는 항상 (0,0)에서 시작
visited[0][0] = True
- BFS 탐색으로 외부 공기(0)가 닿는 칸을 모두 탐색
- visited[i][j] == True면, 외부 공기와 닿는 부분으로 인식함
while q:
x, y = q.popleft()
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = x+dx, y+dy
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
if board[nx][ny] == 0:
visited[nx][ny] = True
q.append((nx, ny))
elif board[nx][ny] == 1:
visited[nx][ny] = True # 치즈도 표시 필요 (중요!)
외부 공기를 만나면 계속 퍼져나가고,
치즈면 visited=True로만 처리 (퍼지지는 않음) → 치즈가 공기와 맞닿아 있는지 판단하기 위해
치즈 녹이기
while True:
air = mark_outside_air()
melt = []
- 매 반복마다 외부 공기를 먼저 탐색해서 air 배열에 저장
for i in range(N):
for j in range(M):
if board[i][j] == 1: # 치즈라면
contact = 0
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
ni, nj = i+dx, j+dy
if 0 <= ni < N and 0 <= nj < M and air[ni][nj] and board[ni][nj] == 0:
contact += 1
if contact >= 2:
melt.append((i, j)) # 녹일 대상 치즈
- 치즈라면, 4방향 중 외부 공기와 접촉한 방향이 2개 이상인지 확인
- 그렇다면 melt 리스트에 위치 추가
종료 조건
if not melt:
return time # 녹일 치즈가 없다 → 모두 사라졌다는 뜻
치즈 녹이기
for i, j in melt:
board[i][j] = 0 # 녹음
time += 1
- melt에 모인 치즈들을 모두 한꺼번에 0으로 변경 (즉, 녹여버림)
- 1시간 경과 → time += 1