백준 7569번: 토마토 (python)

문제

• https://www.acmicpc.net/problem/7569
• 시작점이 여러 개인 너비 우선 탐색 실행하기

기록 포인트

• 시작점이 여러 개인 너비 우선 탐색(BFS)
  • BFS의 탐색 순서를 관리하는 frontier에 여러 개의 시작점을 넣고 시작하면 됨
  • 어떻게 보면, 하나의 시작점으로 BFS를 진행하는 중간부터 시작한다고 볼 수 있음
• 매트릭스에서 상하좌우 탐색하는 방법
  • 좌표(x,y)의 상하좌우 좌표로 이동하는 delta값을 이용해 찾기
  • 이 문제에서는 3차원을 탐색하여 6개 위치를 탐색하며 원리는 동일

    dxs=[-1,1,0,0]
    dys=[0,0,-1,1]
    for dx,dy in zip(dxs, dys):
        x2, y2 = x1+dx, y1+dy
        # 존재하는 위치인지 확인
        if x2 < 0 or x2 >= len(matrix) or y2 < 0 or y2 >= len(matrix):
        continue
        # 필요한 코드 실행

• 각 위치의 탐색 시점을 기록하는 방법 (시작점과의 최소 거리를 기록하는 방법)
  • 매트릭스 상에서 탐색을 진행하므로 매트릭스 좌표(U) 상에 탐색 시점(t)을 기록
  • 해당 좌표(U)의 인접 리스트를 통해 탐색된 다음 좌표(V)는 탐색 시점이 t+1이 됨

접근 방식

• 제출 답안 참고

제출 답안

import sys
from collections import deque

M, N, H = tuple(map(int, sys.stdin.readline().split()))

# 1단계: 매트릭스 구성하기 + 여러 개의 시작점 찾기 (익어 있는 토마토)
# - 여러 개의 익어 있는 토마토를 시작 시점의 frontier로 판단
# - 익어야 하는 개수(goal_count)를 정해, 탐색된 위치의 수가 이 값보다 작은지 확인
matrix = []
frontier = []
goal_count = 0
for h in range(H):
    space = []
    for x in range(N):
        row = list(map(int, sys.stdin.readline().split()))
        space.append(row)
        for y in range(M):
            if row[y] == 1:
                frontier.append((h, x, y))
            elif row[y] == 0:
                goal_count += 1
    matrix.append(space)


# 2단계: 탐색하기
# - 매트릭스 상의 값이 0 이면 아직 탐색이 안된 상태를 의미
# - 매트릭스 상의 값이 1 이상이면 이미 탐색이 된 상태를 의미하며, 그 값은 탐색된 순서를 의미
def BFS(matrix, frontier):
    # 탐색한 위치 개수 초기값 설정
    search_count = 0
    # 만약 이미 탐색할 위치가 없다면 종료
    if goal_count == 0:
        return search_count
    
    # 탐색 소요 시간 초기값 설정
    max_time = 0

    dhs = [0,0,0,0,-1,1]
    dxs = [-1,1,0,0,0,0]
    dys = [0,0,-1,1,0,0]

    frontier = deque(frontier)
    while frontier:
        v1 = frontier.popleft()
        v1_h, v1_x, v1_y = v1
        v1_time = matrix[v1_h][v1_x][v1_y]
        for dh, dx, dy in zip(dhs, dxs, dys):
            h = v1_h + dh
            x = v1_x + dx
            y = v1_y + dy
            # 매트릭스 상에 존재하는 위치인지 확인
            if h < 0 or h >= H or x < 0 or x >= N or y < 0 or y >= M:
                continue
            # 이동 가능한 위치인지 확인
            #  - 값이 -1인 경우, 이동 불가
            #  - 값이 1 이상인 경우, 이미 발견 혹은 탐색된 영역
            if matrix[h][x][y] != 0:
                continue
            # 새로운 위치인 경우
            search_count += 1
            # 해당 위치의 시간 표시
            matrix[h][x][y] = v1_time + 1
            # 소요 시간 계산
            # - 시작점의 시간이 1 부터 시작됨을 고려해 계산
            if max_time < v1_time: 
                max_time = v1_time
            # 탐색할 영역으로 추가
            frontier.append((h, x, y))

    if search_count == goal_count:
        return max_time
    else:
        return -1

print(BFS(matrix, frontier))