728x90
https://www.acmicpc.net/problem/7569
22/09/30
이 문제는 7576번 토마토와 거의 유사한 문제로, 이 문제에서 3차원으로 바꾸기만 하면 되는 문제이다.
https://lighter.tistory.com/34
문제 접근 방식:
문제 접근 방식 자체는 위에서 올린 링크와 같다.
단지 다른 점은 3차원이기 때문에 그래프 입력도 3차원 리스트, BFS도 4방향이 아니라 6방향, 이중 for문이 아니라 3중 for문을 사용했다는 점이다.
아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.
더보기
# 7569번 토마토
# 그래프 이론, 그래프 탐색, BFS
import sys
input = sys.stdin.readline
from collections import deque
M, N, H = map(int, input().rstrip().split())
graph = [[list(map(int, input().rstrip().split())) for _ in range(N)] for _ in range(H)]
compare = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]
for height in range(H):
for row in range(N):
for col in range(M):
if graph[height][row][col] == 1 or graph[height][row][col] == 0:
compare[height][row][col] = 1
else:
compare[height][row][col] = -1
dh = [-1, 1, 0, 0, 0, 0]
dr = [0, 0, -1, 1, 0, 0]
dc = [0, 0, 0, 0, -1, 1]
def BFS():
queue = deque()
for height in range(H):
for row in range(N):
for col in range(M):
if graph[height][row][col] == 1:
queue.append((height, row, col, 0))
final_time = 0
while queue:
height, row, col, time = queue.popleft()
for h, r, c in zip(dh, dr, dc):
nh, nr, nc = height + h, row + r, col + c
if 0<= nh < H and 0 <= nr < N and 0 <= nc < M and graph[nh][nr][nc] == 0:
graph[nh][nr][nc] = 1
queue.append((nh, nr, nc, time+1))
final_time = time
return final_time
def main():
time = BFS()
for height in range(H):
for row in range(N):
for col in range(M):
if graph[height][row][col] != compare[height][row][col]:
print(-1)
return
else:
print(time)
main()
'알고리즘 > 백준 문제 풀이' 카테고리의 다른 글
[Python] 10994번 별 찍기 - 19 (0) | 2022.10.25 |
---|---|
[Python] 20040번 사이클 게임 (0) | 2022.10.25 |
[Python] 4821번 페이지 세기 (0) | 2022.10.24 |
[Python] 25640번 MBTI (0) | 2022.10.24 |
[Python] 11277번 2-SAT - 1 / 11278번 2-SAT - 2 (0) | 2022.10.24 |