https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 3차원을 고려해야 한다는 점에서 조금 특이한 문제였습니다. 다만 3차원 리스트라는 점을 제외하면 이전에 풀었던 토마토 문제(https://www.acmicpc.net/problem/7576)와 비슷한 문제 이므로 어렵지 않게 해결할 수 있습니다.
즉 상자의 위, 아래를 고려해야 하므로 dx, dy 뿐만 아니라 높이를 의미하는 dz 역시 존재해야 합니다. 따라서 for문을 6개로 구분하여 for i in range(6):으로 해결해야 합니다.
문제 해결을 위한 팁
3차원 리스트의 선언은 다음과 같이 선언할 수 있습니다.
graph = [[[0] * m for _ in range(n)]for _ in range(h)]
이렇게 하면 n행 m열의 그래프가 h만큼의 높이를 가지게 됩니다.
접근하는 방법은 다음과 같습니다. 0번째 층의 1행 2열을 접근하려면 graph [0][1][2]로 접근할 수 있고
1번째 층의 2행 3열에 접근하려면 graph[1][2][3]으로 접근할 수 있습니다. 이 3차원 리스트에 지식을 가지고 접근하면 쉽게 해결할 수 있습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
from collections import deque
def bfs(graph, tomato):
count = 0
while tomato:
for _ in range(len(tomato)):
x, y, z = tomato.popleft()
for i in range(6):
nx = x + dx[i]
ny = y + dy[i]
nz = z + dz[i]
if nx < 0 or ny < 0 or nz < 0 or nx >= n or ny >= m or nz >= h:
continue
if graph[nz][nx][ny] == 0:
graph[nz][nx][ny] = 1
tomato.append((nx, ny, nz))
count += 1
return count
m, n, h = map(int, input().split())
graph = [[[0] * m for _ in range(n)] for _ in range(h)]
tomato = deque()
for k in range(h):
for i in range(n):
inputData = list(map(int, input().split()))
for j in range(m):
graph[k][i][j] = inputData[j]
if graph[k][i][j] == 1:
tomato.append((i, j, k))
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
day = bfs(graph, tomato)
numOfZero = 0
for k in range(h):
for i in range(n):
for j in range(m):
if graph[k][i][j] == 0:
numOfZero += 1
if numOfZero == 0:
print(day-1)
else:
print(-1)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 2579번: 계단 오르기(Python) (0) | 2022.01.19 |
|---|---|
| 백준 알고리즘 1003번: 피보나치 함수(Python) (0) | 2022.01.19 |
| 백준 알고리즘 10026번: 적록색약(Python) (0) | 2022.01.15 |
| 백준 알고리즘 4963번: 섬의 개수(Python) (0) | 2022.01.15 |
| 백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.14 |