[BOJ][Python]7569번 풀이

https://www.acmicpc.net/problem/7569

7569번: 토마토

from collections import deque
import sys
ssr = sys.stdin.readline

m,n,h = map(int, ssr().split())
t = [[list(map(int, ssr().split())) for _ in range(n)] for _ in range(h)]
q = deque([])
dp=[(-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)]#h,n,m
for i in range(h):
    for j in range(n):
        for k in range(m):
            if t[i][j][k] == 1:
                q.append((i,j,k,0))
ans = 0
while q:
    tmp = q.popleft()
    for i in dp:
        if 0 <= tmp[0]+i[0] < h and 0 <= tmp[1]+i[1] < n and 0 <= tmp[2]+i[2] < m:
            if t[tmp[0]+i[0]][tmp[1]+i[1]][tmp[2]+i[2]] == 0:
                q.append((tmp[0]+i[0],tmp[1]+i[1],tmp[2]+i[2],tmp[3]+1))
                t[tmp[0]+i[0]][tmp[1]+i[1]][tmp[2]+i[2]] = 1
    ans = tmp[3]
for i in range(h):
    for j in range(n):
        for k in range(m):
            if t[i][j][k] == 0:
                ans = -1
                break
print(ans)

익숙하다 싶더니 같은 문제를 한 번 푼 적이 있었습니다. 물론 그 때는 지금과 달리 2차원 토마토 문제였지만요. 풀이 자체는 완전히 똑같으니까 2차원 문제 풀이도 보고 싶은 분은 아래 링크를 타고 들어가서 확인하시면 됩니다.

https://justduke.tistory.com/219

[BOJ][Python]7576번 풀이

 

문제 자체는 기본적인 bfs 입니다. 다만 항상 하던 것과 달리 3차원 공간을 대상으로 한다는게 약간 다른 점이 되겠네요. 그렇다고 해서 엄청 어려워지진 않았구요. 원소에 접근할 때 인덱스 에러에 주의하고 효율적인 반복문을 생각해보신다면 큰 문제 없이 통과하지 않을까 합니다. 그래도 간단하게 설명하자면 저는 먼저 주어진 입력을 쭉 탐색하면서 익은 토마토를 전부 deque에 넣어줬습니다(이번 문제는 과정이 모두 끝났을 때의 날짜를 출력하는게 포인트이므로 늘 하던대로 좌표 이외의 데이터도 하나 추가해줍니다). 그렇게 하고 deque에서 popleft를 하고 인덱스에러가 나지 않게 조건을 설정해준다음, 익지 않은 토마토가 있으면 날짜 값은 1 증가시키면서 deque에 넣어줍니다. 그렇게 하고 ans에 날짜값을 대입하는데요. 처음부터 모든 토마토가 익어있다면 미리 deque에 넣는 데이터들의 날짜가 전부 0일테니 0을 출력하기 위함이자, 반복문이 진행할수록 날짜가 커지기 때문에 queue의 특성인 선입선출을 이용해서 가장 마지막에 남아있던 데이터의 날짜가 모든 과정이 다 끝났을 때의 날짜이기 때문입니다. 또한 끝났을 때 아직 남은 안익은 토마토가 있을 수 있기 때문에 한 번 더 쭉 탐색을 진행해주고 안익은 토마토를 발견하면 ans에 -1을 대입하고 반복문을 멈춥니다(이미 하나를 발견했다면 뒤를 더 탐색할 이유가 없기 때문). 그리고 ans를 출력해주면 문제를 해결할 수 있습니다.

 

최근에 class 3를 진행하면서 많은 그래프 탐색 문제를 풀었고 이제는 너무 꼬아놓은 문제가 아니면 거의 바로 풀이가 생각이 나는 것 같습니다. 대부분의 코딩 테스트에서도 그래프 탐색 문제들은 하나 이상은 나오는 것 같으니까 익숙해질수록 좋은 것 같네요.