오늘의 학습 키워드
BFS, Breadth-First Search(깊이 우선 탐색)
오늘의 문제
백준 7569번
https://www.acmicpc.net/problem/7569
문제 설명
입출력
BFS 탐색 순서
여섯 방향 방문: BFS 탐색 시 인접한 여섯 방향을 방문하며 토마토가 익는 과정을 확인.
-
시작 위치 설정 및 초기화: 익은 토마토들의 위치를 큐에 넣고 BFS 탐색을 시작한다. 모든 익은 토마토들을 초기 위치로 설정하며, 각 위치에서의 이동 거리는 1로 설정된다. 탐색은 큐가 빌 때까지 진행된다.
-
큐에서 노드를 추출하고 인접한 여섯 방향을 탐색한다: 큐에서 현재 노드를 꺼내고, 그 위치에서 여섯 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)을 탐색한다.
- 각 인접 위치가 유효한 범위 내에 있으며 익지 않은 토마토(0)가 있는 경우에만 큐에 추가하고 익은 토마토로 변경한다.
-
토마토 익는 과정: 각 위치에서 익은 토마토가 주변의 익지 않은 토마토에 영향을 주어 익히는 과정을 진행한다. 인접한 토마토는 현재 위치의 토마토 값에 +1을 하여 갱신된다. 이를 통해 며칠 후에 익게 되는지의 정보를 업데이트한다.
-
큐가 빌 때까지 반복하여 모든 토마토를 익힌다: BFS 탐색을 통해 모든 익은 토마토들이 인접한 토마토에 영향을 줄 때까지 큐를 이용해 반복한다.
-
결과 확인 및 출력: 모든 토마토가 익었는지 확인한다. 만약 익지 않은 토마토가 있다면 -1을 출력하고, 그렇지 않으면 모든 토마토가 익을 때까지 걸린 일수를 출력한다.
BFS 탐색 순서 예시 (입력 예제 2 적용)
탐색 과정 (5×3×2 크기의 상자에서 토마토 익히기)
-
첫 번째 단계:
시작 시점에서 익은 토마토(1)의 위치를 모두 큐에 넣는다. 예제 입력 2에서는 (0, 2, 2) 위치에 익은 토마토가 있어 큐에 추가한다. -
두 번째 단계:
첫 번째 위치 (0, 2, 2)에서 BFS 탐색을 시작한다. 인접한 여섯 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)을 확인하여 익지 않은 토마토(0)가 있는 경우 큐에 추가하고 익힌다.
인접한 토마토들이 익으면서 큐에는 새로운 익은 토마토들의 위치가 추가된다. -
세 번째 단계:
두 번째 날에는 인접한 토마토들이 계속 익으며 큐에 추가된다. 이 과정은 모든 익지 않은 토마토가 익을 때까지 계속된다. -
네 번째 단계:
네 번째 날까지 모든 토마토가 익게 된다. 상자의 모든 칸을 탐색하여 익지 않은 토마토(0)가 없음을 확인한다. -
결과 출력:
모든 토마토가 익었으므로 최소 4일이 걸린다. 따라서 결과는 4이다.
따라서 BFS 탐색 순서는 시작 위치에서 모든 방향으로 확장되며, 모든 토마토가 익는 데 걸리는 시간은 4일이다.
1. 기본 설정 및 입력 처리
import sys
from collections import deque
m,n,h = map(int,input().split()) # mn크기, h상자수
graph = []
queue = deque([])-
import sys와 from collections import deque: 빠른 입력과 BFS 탐색을 위해 필요한 라이브러리를 임포트한다. -
m, n, h = map(int, input().split()): 상자의 크기(M, N)와 상자 수(H)를 입력받는다. -
graph = []와 queue = deque([]): 상자 정보를 저장할 리스트와 BFS 탐색을 위한 큐를 초기화한다.
2. 그래프 구성 및 익은 토마토 위치 초기화
tmp.append(list(map(int,sys.stdin.readline().split())))
for k in range(m):
if tmp[j][k]==1:
queue.append([i,j,k])
graph.append(tmp)-
for i in range(h): 각 상자(h 개)에 대해 토마토 정보를 입력받는다. -
tmp.append(list(map(int, sys.stdin.readline().split()))): 각 줄에 대한 토마토 정보를 리스트로 저장한다. -
if tmp[j][k] == 1: 익은 토마토(1)의 위치를 큐에 추가하여 BFS 탐색의 시작점으로 설정한다.
3. BFS 탐색 정의 및 초기화
dx = [-1,1,0,0,0,0]
dy = [0,0,1,-1,0,0]
dz = [0,0,0,0,1,-1]
while(queue):
x,y,z = queue.popleft()
for i in range(6):
a = x+dx[i]
b = y+dy[i]
c = z+dz[i]
if 0<=a<h and 0<=b<n and 0<=c<m and graph[a][b][c]==0:
queue.append([a,b,c])
graph[a][b][c] = graph[x][y][z]+1-
dx, dy, dz = [...]: 여섯 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)을 나타내는 리스트를 정의한다. -
while(queue): 큐가 빌 때까지 BFS 탐색을 진행한다. -
x, y, z = queue.popleft(): 큐에서 현재 위치를 꺼낸다. -
for i in range(6): 여섯 방향을 탐색하며 인접한 토마토들을 익힌다. -
if 0 <= a < h and 0 <= b < n and 0 <= c < m and graph[a][b][c] == 0: 인접 위치가 유효하고 익지 않은 토마토(0)가 있는 경우에만 큐에 추가하고 익힌다.
4. 결과 확인 및 출력
day = 0
for i in graph:
for j in i:
for k in j:
if k==0:
print(-1)
exit(0)
day = max(day,max(j))
print(day-1)-
for i in graph: 모든 상자를 확인하여 익지 않은 토마토(0)가 있는지 확인한다. -
if k == 0: 익지 않은 토마토가 있으면 -1을 출력하고 프로그램을 종료한다. -
day = max(day, max(j)): 모든 토마토가 익을 때까지 걸린 일수를 갱신한다. -
print(day - 1): 시작을 1로 표현했으므로 결과에서 1을 빼서 출력한다.
전체 풀이
import sys
from collections import deque
m,n,h = map(int,input().split()) # mn크기, h상자수
graph = []
queue = deque([])
for i in range(h):
tmp = []
for j in range(n):
tmp.append(list(map(int,sys.stdin.readline().split())))
for k in range(m):
if tmp[j][k]==1:
queue.append([i,j,k])
graph.append(tmp)
dx = [-1,1,0,0,0,0]
dy = [0,0,1,-1,0,0]
dz = [0,0,0,0,1,-1]
while(queue):
x,y,z = queue.popleft()
for i in range(6):
a = x+dx[i]
b = y+dy[i]
c = z+dz[i]
if 0<=a<h and 0<=b<n and 0<=c<m and graph[a][b][c]==0:
queue.append([a,b,c])
graph[a][b][c] = graph[x][y][z]+1
day = 0
for i in graph:
for j in i:
for k in j:
if k==0:
print(-1)
exit(0)
day = max(day,max(j))
print(day-1)