2638. 치즈 [BAEKJOON / Python]
문제
https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.
치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다.
input =
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
output = 4
전체 코드
# 치즈
from collections import deque
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
cnt = 0
while True:
visited = [[0] * m for _ in range(n)]
queue = deque()
queue.append((0, 0))
visited[0][0] = 1
melting = {} # 좌표를 (a, b): 1 형식으로 넣고 두 변 이상 맞닿아 있을 경우 0으로 처리
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
if maps[nx][ny] == 0:
visited[nx][ny] = 1
queue.append((nx, ny))
# 치즈가 있는 경우
else:
# 해당 좌표가 딕셔너리에 없다면
if (nx, ny) not in melting:
# 새로 딕셔너리에 추가
melting[(nx, ny)] = 1
# 이미 좌표가 있다면
else:
# 해당 Key에 1을 추가
melting[(nx, ny)] += 1
# 딕셔너리에 아무것도 담기지 않았다면 while True문 중단 => 더 이상 녹을 치즈가 없음
if len(melting) == 0:
break
# 딕셔너리에 값들이 담겨있다면
else:
# k에는 key값, v에는 value값 할당
for k, v in melting.items():
# 좌표가 두번 이상 들어갔다면
if v >= 2:
maps[k[0]][k[1]] = 0 # 해당 키값의 좌표(x, y)를 0으로 만든다 => 두변 이상 맞닿았기 때문에 치즈가 녹음
cnt += 1 # for문이 끝날 때마다 치즈가 녹는 한시간이 지나므로 1을 더해줌
print(cnt)
문제 풀이 포인트
- BFS
- 치즈가 있는 좌표에서 0(공기)가 맞닿아 있는 부분이 몇번 있는지 딕셔너리 형태로 좌표와 횟수를 저장한다.
로직
- 4방향 탐색으로 치즈와 맞닿아있는 0의 개수를 세어준다. 이때 '좌표: 횟수' 형태로 딕셔너리 변수에 할당한다.
- while True문으로 무한반복하며 딕셔너리에 들어갈 좌표 값을 계속해서 찾은 후 녹을 치즈의 좌표를 0으로 만들어준다.
- 0으로 만들어줄 때 치즈가 녹는 시간인 cnt 변수에 1씩 더해준다. (한시간마다 녹기 때문)
코드 디테일
while True문으로 치즈가 녹을 때 까지 반복하기
from collections import deque
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
cnt = 0
while True:
visited = [[0] * m for _ in range(n)]
queue = deque()
queue.append((0, 0))
visited[0][0] = 1
melting = {} # 좌표를 (a, b): 1 형식으로 넣고 두 변 이상 맞닿아 있을 경우 0으로 처리
기존 BFS 문제를 풀 때에는 while queue(deque 기능하는 변수)로 반복문을 설정하여 그래프를 이동해주었지만,
치즈 문제는 방향을 탐색하는 while queue문이 치즈가 한 번 녹는 구조이기 때문에
치즈가 다 녹을 때 까지 while queue(방향 탐색 반복문)을 계속해서 반복하기 위해서는 while True문을 사용해야 한다.
치즈가 한 번 녹는 반복문을 실행했을 경우 다시 방문 리스트와 deque 기능을 하는 변수, 딕셔너리를 모두 새로 만들어주어야 한다.
왜냐하면 치즈가 녹은 좌표는 0으로 새롭게 할당해주었고, 새로운 그래프에서 다시 탐색해주어야 하기 때문이다!
4방향 탐색으로 치즈 발견
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
if maps[nx][ny] == 0:
visited[nx][ny] = 1
queue.append((nx, ny))
# 치즈가 있는 경우
else:
# 해당 좌표가 딕셔너리에 없다면
if (nx, ny) not in melting:
# 새로 딕셔너리에 추가
melting[(nx, ny)] = 1
# 이미 좌표가 있다면
else:
# 해당 Key에 1을 추가
melting[(nx, ny)] += 1
4방향 탐색으로 치즈가 있는 자리를 탐색해준다.
만약 4방향 탐색 시 치즈가 있는 좌표를 발견한다면
melting[(nx, ny)] = 1 구문을 통해 튜플 형태로 좌표를 key값으로 할당하고, value값은 좌표 발견 횟수를 산정한다.
전체적인 좌표가 이러한 형태일 때 파란색과 빨간색 칸은 (0, 0)부터 4방향 탐색을 시작한 현재 위치라고 가정해보자.
4방향 탐색 중 처음으로 치즈를 발견한 위치를 파란색 칸이라고 하자.
그렇다면 현재 파란색 위치에서 치즈를 발견했으므로 (1, 4)의 값이 melting 딕셔너리에 들어가게 되는 것이다.
치즈의 위치와 노출된 횟수가 이렇게 담기게 된다.
이후 파란색을 지나고 현재 위치가 빨간색이 될 때 동일한 치즈가 발견된다. 그렇다면 위의 딕셔너리에 있는 치즈 위치인 (1, 4)의 값은 2로 변경된다.
딕셔너리 검사 => 두번 이상 발견된 치즈는 녹는다 => 0으로 처리
# 딕셔너리에 아무것도 담기지 않았다면 while True문 중단 => 더 이상 녹을 치즈가 없음
if len(melting) == 0:
break
# 딕셔너리에 값들이 담겨있다면
else:
# k에는 key값, v에는 value값 할당
for k, v in melting.items():
# 좌표가 두번 이상 들어갔다면
if v >= 2:
maps[k[0]][k[1]] = 0
cnt += 1
print(cnt)위의 4방향 탐색 반복문이 끝나면 이 구문이 실행된다.
현재 (1, 4) : 2 값 이외에도 치즈의 위치와 발견 횟수가 melting 딕셔너리에 저장되어있다.
.items() 함수로 키와 값을 각각의 k, v 변수에 할당해준다.
발견된 횟수가 2번 이상일 경우 (if v >= 2) 좌표에 있는 치즈를 0으로 만들어 준다. (maps[k[0]k[1] = 0)
해당 반복문이 끝날 때 마다 cnt에 1씩 더해주며 치즈가 모두 녹는 시간을 측정한다.
4방향 탐색 후에도 melting에 아무런 값이 들어오지 않았다면 치즈가 모두 녹은것이므로
while True문을 if len(melting) == 0: break로 반복문을 중단해준다. 이 구문이 없을 시 무한반복하게 되므로 필!수!