Python3
문제
https://www.acmicpc.net/problem/7569
키워드
- 그래프 탐색
- 너비 우선 탐색
문제 풀이
문제 요구사항
- 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
- 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다.
- 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.
- 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램
(단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.)
변수 및 함수 설명
- m, n, h: M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수, 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. (단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100)
- dy, dx, dz: 위, 아래, 왼쪽, 오른쪽, 앞, 뒤로 이동
- adjMatrix: 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보
정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸 - bfsQueue: bfs를 위한 큐
- visited: 방문처리를 위한 리스트
- ny, nx, nz: 다음으로 이동할 칸
- cnt: 토마토가 익는데 필요한 최소 일수
- bfs(): bfs를 처리하는 함수
풀이
(입력 및 선언)
- 상자 정보인 m, n, h를 입력받는다
- dy, dx, dz를 선언한다. 총 6개 방향 이동 가능.
- adjMatrix는 3차원 배열이다. 임시 배열인 arr 안에 가로 세로가 있는 토마토를 입력받고, 3차원 배열 안에 넣어준다.
(익은 토마토 찾기)
- 익은 토마토의 위치를 찾기 위해서는 adjMatrix가 1이고, 방문하지 않은 곳이어야 한다.
- 해당 조건에 맞는 익은 토마토를 찾으면 큐에 넣고 방문 처리를 해준다.
- 큐에 한 번에 넣고 bfs 함수를 실행한다. (익은 토마토는 동시에 주변을 익히기 때문)
(bfs 함수)
- 큐에 원소가 있을 때까지 반복한다
- 가장 왼쪽에 위치한 원소를 pop하고 curY, curX, curZ 변수 안에 저장한다.
- 토마토는 인접한 6개의 방향을 이동할 수 있다.
- (1) 다음 위치는 토마토 상자 내에 위치해야 하며, (2) 방문하지 않은 곳이고, (3) 토마토 상태가 -1(토마토가 없는 것)이 아니어야 한다.
- 조건을 만족하면 다음 이동할 위치를 큐에 넣고, 방문처리를 하고, adjMatrix를 누적값 + 1 해준다.
(최소 일수 구하기)
- adjMatrix를 돌며 최소 일수를 구한다.
- 만약 0이 하나라도 있으면 -1을 출력하고 종료한다.
이때, break가 아닌 exit()을 사용해야 하는 이유?
break는 단순히 반복문 하나만을 종료하는 것이다. 따라서 토마토가 0인 부분마다 -1을 출력할 것이다. 그래서 프로그램을 종료시키는 exit()을 사용해야 한다. - cnt에 adjMatrix 중 최댓값을 넣는다.
최소 일수지만 최댓값을 구하는 이유?
토마토가 다 익기 위해 최소한으로 필요한 시간이 리스트에 들어 있는 최댓값이다. adjMatrix에서 최솟값을 출력하면, 다 익지 못한 채 남아 있는 토마토가 있을 것이다. - 토마토가 이미 모두 익어 있는 경우는 0을 출력하라고 했다. 따라서 adjMatrix에 모든 토마토가 1이면 cnt-1을 출력하므로 0이 된다. 이 조건을 위한 부가적인 코드는 쓸 필요가 없다.
최종 코드
from collections import deque
m, n, h = map(int, input().split())
dy = [-1, 0, 1, 0, 0, 0]
dx = [0, 1, 0, -1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
adjMatrix = []
bfsQueue = deque([])
visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(h)]
cnt = 0
for i in range(h):
arr = []
for j in range(n):
arr.append(list(map(int, input().split())))
adjMatrix.append(arr)
def bfs():
while bfsQueue:
curY, curX, curZ = bfsQueue.popleft()
for i in range(6):
ny = curY + dy[i]
nx = curX + dx[i]
nz = curZ + dz[i]
if ny < 0 or nx < 0 or nz < 0 or ny >= h or nx >= n or nz >= m:
continue
if visited[ny][nx][nz] != 0:
continue
if adjMatrix[ny][nx][nz] != 0:
continue
bfsQueue.append((ny, nx, nz))
visited[ny][nx][nz] = 1
adjMatrix[ny][nx][nz] = adjMatrix[curY][curX][curZ] + 1
for i in range(h):
for j in range(n):
for k in range(m):
if adjMatrix[i][j][k] == 1 and visited[i][j][k] == 0:
bfsQueue.append((i, j, k))
visited[i][j][k] = 1
bfs()
for i in adjMatrix:
for j in i:
for k in j:
if k == 0:
print(-1)
exit()
cnt = max(cnt, max(j))
print(cnt-1)
피드백
list out of range 오류가 계속 났다.
처음에는 dy, dx를 5개, dz를 6개로 선언해서 안 맞았다. 방향이 여러 개로 늘어나니까 신경을 안 쓰고 지나가면 오류를 찾기가 까다로웠다.
이후에는 visited 배열의 크기를 잘못 설정했는데, 반복문과 헷갈려 h, m, n 순으로 만들었다. 직접 visited 배열을 출력하면서 해결했다.
그리고 bfs함수 안에 있는 첫 번째 if문 설정도 문제가 있었다. h <= ny < 0, n <= ny < 0, m <= nz <0으로 썼더니 계속 list out of range 오류가 났다. 그래서 하나씩 풀어 썼더니 고쳐졌다. 흠.. 뭐가 다르지
I mean