[Baekjoon 7569 / python / 골드5] 토마토

from collections import deque

import sys

input = sys.stdin.readline

M, N, H = map(int, input().split())  # 가로, 세로, 높이 5, 3, 2

box = []

for i in range(N * H):  # 토마토 입력받기

    box.append(list(map(int, input().split())))

visited = [[False] * M for _ in range(N * H)]  # 방문목록 box와 똑같이 만들기

def goingNogoing(box, x, y, visited):  # 익힐수있는지 고민하는함수

    if 0 <= x < N * H and 0 <= y < M and visited[x][y] == False and box[x][y] == 0:  # 좌표가 box안에있으며 미방문이고 값이 0이어야한다

        return True

    return False

def tomato(box, visited):  # bfs

    queue = deque([])

    cnt = 0  # 안익은토마토 개수 담을 변수

    day = 0  # 다익는데 몇일걸리는지 담을 변수

    for x in range(N * H): # 0~2

        for y in range(M):  # 0~4

            if box[x][y] == 1:  # 익은 토마토를 큐에 추가

                queue.append((x, y))

                visited[x][y] = True  # 익은곳 방문체크

            elif box[x][y] == 0:  # 안익은 토마토일 경우 cnt += 1

                cnt += 1

    if cnt == 0: return 0

   

    while queue:

        for _ in range(len(queue)):  # 큐에 있는 토마토들 주변을 모두 익게 만든 뒤 날짜를 하루 추가해야 한다

            x, y = queue.popleft()  # x, y 좌표 꺼내고, 상하좌우앞뒤 전부 체크하기

           

            if goingNogoing(box, x - 1, y, visited) and x//N == (x-1)//N:  # 앞, 앞뒤는 층을 침범할 가능성이 있으므로 같은 층일때만 익힌다

                visited[x-1][y] = True  # 방문체크(익혔음)

                cnt -= 1  # 익혔으니 안익은토마토개수 -1

                queue.append((x-1, y))  # 익혔으니 큐에 넣기

            if goingNogoing(box, x + 1, y, visited) and x//N == (x+1)//N :  # 뒤, 앞뒤는 층을 침범할 가능성이 있으므로 같은 층일때만 익힌다

                visited[x+1][y] = True

                cnt -= 1

                queue.append((x+1, y))

            if goingNogoing(box, x, y - 1, visited):  # 좌

                visited[x][y-1] = True

                cnt -= 1

                queue.append((x, y-1))

            if goingNogoing(box, x, y + 1, visited):  # 우

                visited[x][y+1] = True

                cnt -= 1

                queue.append((x, y+1))

           

            if goingNogoing(box, x + N, y, visited):  # 하

                visited[x+N][y] = True

                cnt -= 1

                queue.append((x+N, y))

            if goingNogoing(box, x - N, y, visited):  # 상

                visited[x-N][y] = True

                cnt -= 1

                queue.append((x-N, y))

        day += 1 # 다익혔으면 하루 추가하기

        if cnt == 0: return day  # 하루 지날때마다 다 익었는지 검사

    if cnt == 0: return day  # 마지막에 한번 더 검사

    else: return -1

print(tomato(box, visited))

 

BFS 문제이다. 미로 찾기 등의 문제와 흡사하지만, 이 문제는 상하좌우 + 높이까지 고려하기 때문에 신경 쓸 게 조금 더 많다. 

 

3차원 배열로도 풀 수 있지만 난 2차원 배열이 익숙해 2차원 배열로 해결했다. 2차원 배열은 층을 구분할 조건문 하나만 추가해주면 된다. 상하앞뒤좌우 6방향이라고 할 때, 앞뒤(x가 바뀔 때)를 탐색할 때만 조건을 걸어주면 된다.

앞 : x // N == (x - 1) // N

뒤 : x // N == (x + 1) // N

이 2개의 조건을 각각 추가하면 된다.

 

나머지는 일반적인 BFS 알고리즘과 크게 차이가 없다. 익은 토마토(1)들을 먼저 큐에 넣어주고, 안익은 토마토(0)의 개수만큼 cnt값을 올린다. 

이후 큐에서 노드를 꺼낼 때마다 상하앞뒤좌우 좌표를 모두 탐색하되,

1. x,y좌표가 박스 안에 있고

2. visited가 False이며(미방문)

3. 값이 0인(안익은 토마토)

이 3개 조건을 만족할 경우 방문하면 된다. 

 

이렇게 BFS를 돌리고, 몇번 째 반복에서 모든 토마토가 익었는지(1이 되었는지) 출력하면 된다.