[BFS] - G5_7569 토마토

1️⃣ - 처음 생각한 풀이

1.  3차원 배열을 만들어서 데이터를 넣는다.
2.  전부 방문하면서 1일 경우, 주변 토마토들을 익힌다.
3.  토마토를 익힐 수 없을 때, 반복을 종료하고 년도, 상태를 확인하고 출력한다

이런 식으로 풀이를 생각했었는데, 3차원으로 생각을 하려다보니 계속 복잡해지고 헷갈려서 자꾸 답이 틀려서 다른 방식을 찾아봤다.

 

 

2️⃣ - 두 번째 풀이

1. 3차원 배열에서 1을 전부 queue에 담는다. - 담으면서 방문처리
2. bfs로 queue에 있는 좌표들을 빼면서 근처 좌표들을 queue에 다시 넣고 익히는 과정을 반복한다. - queue에 다음 좌표들을 넣을 때 년도를 같이 넣어준다.
3. 바뀐 배열을 처음부터 비교해서 가장 큰 값 -1을 출력한다

 

---

from sys import stdin as s
from collections import deque
import time
s =open('input.txt','rt')

M , N , H = map(int,s.readline().split())

arr = [[list(map(int,s.readline().split())) for _ in range(N)] for _ in range(H)]
visited = [[[False] * M for _ in range(N)] for _ in range(H)]

queue = deque()

dh = [0,0,0,0,-1,1]
dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]

answer = 0

def bfs():
    while queue:
        x,y,z = queue.popleft()

        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dh[i]

            if nx < 0 or nx >= H or ny < 0 or ny >= N or nz < 0 or nz >= M:
                continue

            if arr[nx][ny][nz] == 0 and not visited[nx][ny][nz]:
                queue.append((nx,ny,nz)) 
                arr[nx][ny][nz] = arr[x][y][z] +1
                visited[nx][ny][nz] = True



if __name__ == "__main__" :

    for a in range(H):
        for b in range(N):
            for c in range(M):
                if arr[a][b][c] == 1 and not visited[a][b][c]:
                    queue.append((a,b,c))
                    visited[a][b][c] = True

    bfs()


    for a in arr:
        for b in a:
            for c in b:
                if c == 0 :
                    print(-1)
                    exit()
            answer = max(answer,max(b))

    print(answer - 1)

 

여기서 이렇게 제출했을 때는 2000ms 정도의 속도가 나왔는데, 아래의 코드로는 거의 4000ms가 나와서 원인을 찾아봤다.

 

from sys import stdin as s
from collections import deque
import time
M, N, H = map(int, s.readline().split())

dz = [0, -1, 0, 0, 1, 0]
dy = [0, 0, 1, 0, 0, -1]
dx = [1, 0, 0, -1, 0, 0]

tomato = [[list(map(int,s.readline().split())) for _j in range(N)] for _k in range(H)]
visited = [[[False for _i in range(M)] for _j in range(N)] for _k in range(H)]

days = 0
'''
이렇게 보면 층같이 보인다.
for i in tomato:
    print(i)
'''

# print(tomato)
queue = deque()

for _i in range(H):
    for _j in range(N):
        for _k in range(M):
            if tomato[_i][_j][_k] == 1 and visited[_i][_j][_k]:
                queue.append((_i, _j, _k))


while len(queue) != 0:
    z,y,x = queue.popleft()
    visited[z][y][x] = True
    for i in range(6):
        new_z = z + dz[i]
        new_y = y + dy[i]
        new_x = x + dx[i]

        # 범위 확인
        if new_z < 0 or new_z >= H or new_y < 0 or new_y >= N or new_x < 0 or new_x >= M:
            continue

        # 방문 확인
        if not visited[new_z][new_y][new_x] and tomato[new_z][new_y][new_x] == 0:
            queue.append([new_z, new_y, new_x])
            tomato[new_z][new_y][new_x] = tomato[z][y][x] + 1



for _i in range(H):
    for _j in range(N):
        for _k in range(M):
            if tomato[_i][_j][_k] == 0:
                print(-1)
                exit(0)    
        days = max(days, max(tomato[_i][_j]))

print(days-1)

 

중간에 bfs를 함수로 넣어주고 말고의 차이인데 속도 차이가 거의 2배가 난다.

 

해당하는 내용은 아래 블로그에서 확인 할 수 있다.

https://8iggy.tistory.com/155

Python 함수 코드가 일반 코드보다 빠른 이유