728x90
단계별로 풀어보기 DFS와 BFS의 7단계 문제
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마
www.acmicpc.net
5단계 문제인 7576번 문제의 3차원 버전이다. 따라서 위, 아래만 더 검사하면 된다. 앞, 뒤, 오른쪽, 왼쪽은 2차원일 때에도 검사했으니까.
from sys import stdin
m, n, h = list(map(int, stdin.readline().split()))
matrix = []
for i in range(h):
matrix.append([])
count = 0
minus = 0
zero = 0
import collections
q = collections.deque()
one = []
for i in range(h):
for j in range(n):
temp = list(map(int, stdin.readline().split()))
matrix[i].append(temp)
count += temp.count(1)
minus += temp.count(-1)
zero += temp.count(0)
for k in range(m):
if temp[k] == 1:
q.append((i, j, k, 0))
if zero == 0:
print(0)
else:
ripen = 0
result = 0
visited = [[[False] * m for j in range(n)] for i in range(h)]
while q:
cur = q.popleft()
if not visited[cur[0]][cur[1]][cur[2]]:
visited[cur[0]][cur[1]][cur[2]] = True
matrix[cur[0]][cur[1]][cur[2]] = 1
ripen += 1
result = cur[3]
else:
continue
if cur[0] + 1 < h and matrix[cur[0] + 1][cur[1]][cur[2]] == 0 and not visited[cur[0] + 1][cur[1]][cur[2]]:
q.append((cur[0] + 1, cur[1], cur[2], cur[3] + 1))
if cur[1] + 1 < n and matrix[cur[0]][cur[1] + 1][cur[2]] == 0 and not visited[cur[0]][cur[1] + 1][cur[2]]:
q.append((cur[0], cur[1] + 1, cur[2], cur[3] + 1))
if cur[0] - 1 >= 0 and matrix[cur[0] - 1][cur[1]][cur[2]] == 0 and not visited[cur[0] - 1][cur[1]][cur[2]]:
q.append((cur[0] - 1, cur[1], cur[2], cur[3] + 1))
if cur[1] - 1 >= 0 and matrix[cur[0]][cur[1] - 1][cur[2]] == 0 and not visited[cur[0]][cur[1] - 1][cur[2]]:
q.append((cur[0], cur[1] - 1, cur[2], cur[3] + 1))
if cur[2] + 1 < m and matrix[cur[0]][cur[1]][cur[2] + 1] == 0 and not visited[cur[0]][cur[1]][cur[2] + 1]:
q.append((cur[0], cur[1], cur[2] + 1, cur[3] + 1))
if cur[2] - 1 >= 0 and matrix[cur[0]][cur[1]][cur[2] - 1] == 0 and not visited[cur[0]][cur[1]][cur[2] - 1]:
q.append((cur[0], cur[1], cur[2] - 1, cur[3] + 1))
if ripen == m * n * h - minus:
print(result)
else:
print(-1)
728x90
'알고리즘 문제' 카테고리의 다른 글
| [백준] 2206번 벽 부수고 이동하기 (미해결) (0) | 2020.01.11 |
|---|---|
| [백준] 1697 숨바꼭질 (0) | 2020.01.10 |
| [백준] 7576번 토마토 (0) | 2020.01.10 |
| [백준] 2178번 미로 탐색 (0) | 2020.01.10 |
| [백준] 1330번 두 수 비교하기 (0) | 2020.01.10 |