[BFS] 백준 7569번 토마토 with Python3

illustrated  by  あすてろid  

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

7569번: 토마토

문제

 

정답 풀이

from collections import deque
import sys
input = sys.stdin.readline
# 앞 뒤 좌 우 아래 위
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]


def bfs():
    while q:
        a, b, c = q.popleft()  # 행 열 높이
        visit[c][a][b] = 1

        for i in range(6):
            x = a + dx[i]
            y = b + dy[i]
            z = c + dz[i]

            if 0 <= x < n and 0 <= y < m and 0 <= z < h and box[z][x][y] == 0 and visit[z][x][y] == 0:
                q.append([x, y, z])
                box[z][x][y] = box[c][a][b] + 1 
                #익게 하는 좌표의 값에 1을 더한 것을 익게되는 좌표에 넣으므로
                #각 원소에 어느날 익는지가 값으로 남는다
                visit[z][x][y] = 1


m, n, h = map(int, input().split())
box = [[] for i in range(h)]
# box와 똑같은 3차원 리스트 만들기
visit = [[[0 for i in range(m)] for i in range(n)] for i in range(h)]

q = deque()
isTrue = False
st = False

# box에 input들을 넣어주기
for i in range(h):
    for j in range(n):
        box[i].append(list(map(int, input().split())))
#box [ h : 높이][ r: 행][ c : 열]


# 시작 노드들을 전부 큐에 append
for z in range(h):
    for x in range(n):
        for y in range(m):
            if box[z][x][y] == 1:
                q.append([x, y, z])

# 시작노드들을 모두 넣었기에
bfs()
#실행되면 가능한 모든 토마토가 익게 된다. 

#불가능한 경우와, 다 익었을 경우 소요 일 수를 체크하는 for문
max_num = 0
for z in range(h):  # 높이
    for x in range(n):  # 행
        for y in range(m):  # 열
            if box[z][x][y] == 0:  # 아직도 익지 않은 토마토가 있을경우 = 불가능
                isTrue = True
            max_num = max(max_num, box[z][x][y])


if isTrue == True:  # 불가능한 경우이기에 추가
    print(-1)
else:
    print(max_num - 1)
#익게 하는 좌표의 값에 1을 더한 것을 익게되는 좌표에 넣으므로, 각 원소에 어느날 익는지가 값으로 남는다
#시작이 1이기에 -1 만 해주면 됌.

출처:https://pacific-ocean.tistory.com/297

해석

3차원 좌표를 사용했다. 이렇게 간단하게 구현할 수 있었는데 괜히 쉽게 가려다가 오히려 어려워져서 직접 풀이 구현에 막혔다.

 

미로 탐색처럼 이전 원소의 값에 +1 한 값을 다음 원소의 값에 넣어주면 각각의 원소가 얼마나 걸렸는지 알 수 있다는 것을 활용했다.

 

그리고 bfs 함수 실행 이후 가능한 모든 토마토가 익게 됨으로 0이 아직도 남아있는지만 체크하면 되는 짜임새있는 코드라고 생각한다.

 

그리고 시작 노드가 여러개일 경우, 미리 큐에 넣어 놓고 bfs를 실행하면 된다는 것을 또 이번에 알수 있었다.

 

내 풀이 -  실패 -

from collections import deque


n, m, h = map(int, input().split())
# m = r, n = c , iz = r - m*h

box = [list(map(int, input().split())) for _ in range(m*h)]


# print(box)
# print(visited)

# 앞 우 뒤 좌 상 하
dy = [-1, 0, 1, 0, 0, 0]
dx = [0, 1, 0, -1, m, -m]


def bfs(r, c):

    if visited[r][c] == True:
        return

    # 불가능한 경우인지 판명용
    if box[r][c] == 0:
        visited[r][c] = True
        count = 0
        for i in range(6):
            nx = r + dx[i]
            ny = c + dy[i]

            if (0 <= nx < m*h) and (0 <= ny < n) and box[nx][ny] == -1:
                count += 1
        if count == 6:
            return 1

    elif box[r][c] == 1:
        que = deque([])
        que.append([r, c])
        visited[r][c] = True

        while que:
            [x, y] = que.popleft()
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]

                if (0 <= nx < m*h) and (0 <= ny < n) and visited[nx][ny] == False and box[nx][ny] == 0:

                    visited[nx][ny] = 1
                    # print(f'나는 x:{nx} / 나는 y:{y}')
                    que.append([nx, ny])
                    box[nx][ny] += 1


for k in range(1, m*h):
    # 매일 방문 기록 초기화
    visited = [[False] * (n) for _ in range(m*h)]

    for i in range(m*h):
        for j in range(n):
            if box[i][j] == 1:
                bfs(i, j)
            elif box[i][j] == -1:
                visited[i][j] == True
            else:  # 0일 경우
                a = bfs(i, j)
                if a == 1:
                    print('-1')
                    exit()
                visited[i][j] == True

    if False not in visited:
        print(k)
        break

해설

상기했듯이 3차원 배열이라는 것을 깊이 고민하지않고 x 값을 m * h만큼 이동만 하면 된다고 생각했다. 

처음엔 괜찮은 아이디어인줄 알았는데 높이가 다른 박스로 앞 뒤 이동할때 넘어갈 수 있다는 사실을 이만큼 쓰고 깨달았다...

 

불가능한 경우를 탐색하는 경우 0을 만나면 상하좌우앞뒤가 -1인지 검증하는 식으로 구현했다. 하지만 비효율적이었다.

 

미로 탐색을 통해 이동 전 박스 값에 1을 더한 것을 이동 후 원소에 넣으면 어떤 원소든 몇일 혹은 몇번이 걸렸는지 알 수 있음을 배웠음에도 깊게 생각하지 않았던거 같다.

 

다음부턴 코드 작성이전에 충분히 생각을 하고 시도해야겠다...