[백준] 7576번 : 토마토 (🥇골드 5) (Python)

문제 바로 가기

7576번: 토마토

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2023-02-10

 

from collections import deque


# 입력값 처리 및 필요 변수 선언
m, n = tuple(map(int, input().split()))

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

visited = [
    [False] * m
    for _ in range(n)
]

days = [
    [0] * m
    for _ in range(n)
]

q = deque()


# (2차원) 배열 visited, days 추가 세팅
answer_0_flag = True

for r in range(n):
    for c in range(m):
        if box[r][c] == -1:
            visited[r][c] = True
            days[r][c] = -1
        if box[r][c] == 0:
            answer_0_flag = False


drs, dcs = [1, -1, 0, 0], [0, 0, 1, -1]


# BFS 및 관련 함수 선언
def in_range(r, c):
    return r >= 0 and r < n and c >= 0 and c < m

def can_go(r, c):
    return in_range(r, c) and not visited[r][c]

def bfs():
    while q:
        r, c = q.popleft()

        for dr, dc in zip(drs, dcs):
            nr, nc = r + dr, c + dc

            if can_go(nr, nc) and box[nr][nc] == 0:
                visited[nr][nc] = True
                days[nr][nc] += (days[r][c] + 1)
                box[nr][nc] = 1
                q.append((nr, nc))


# 토마토가 익는 과정 수행
for r in range(n):
    for c in range(m):
        if box[r][c] == 1:
            visited[r][c] = True
            days[r][c] = 0 # 없어도 되는 코드
            q.append((r, c))
bfs()


# 결과 분석
max_days = 0

def analyze_result():
    global max_days

    if answer_0_flag:
        return 0

    for r in range(n):
        for c in range(m):
            max_days = max(days[r][c], max_days)
            if box[r][c] == 0:
                return -1
    return max_days


print(analyze_result())

 

풀이 로직

• 토마토 박스에서 토마토들이 익는 과정을 격자에서 숫자 1이 있는 칸부터 BFS 방법으로 탐색해나가는 과정이라 생각하고 문제를 풀었다.
• 3개의 2차원 격자를 선언하고 풀었는데, 2개만 사용해도 풀 순 있을 것 같다.
• 숫자가 1인 칸의 위치를 모두 큐 자료구조에 넣어주고, 칸의 상하좌우를 탐색하여 0이 있는 칸을 다음 탐색 대상으로 삼았다. (파이썬 특성 상 queue 대신 deque 자료구조를 선언해주었다)
  • 다음 칸을 탐색하는 시기는 토마도 박스로 치면 다음 날이 되었을 때이므로 이를 days 격자에 반영하였다.
• 모든 칸을 탐색한 후 days 격자에 반영된 결과에 따라 올바른 답을 출력하도록 코드를 작성했다.
  • 처음 입력 받을 때 0인 칸이 없으면, 이미 모든 토마토가 익어있다는 의미이므로 바로 0을 출력한다.
  • 탐색이 끝난 후 0인 칸이 days 격자에 남아있으면, 토마토가 모두 익지 못하는 상태이므로 -1을 출력한다.
  • 위 경우가 모두 아니라면, days 격자에 있는 수들의 최댓값이 토마토가 모두 익을 때까지 걸린 최소 시간이므로, 격자를 순회하여 이 값을 찾아 출력한다.

 

문제 접근 과정 및 느낀점

• BFS(너비 우선 탐색) 방법의 최단 거리 이동 문제 유형이라 생각하고 풀었다.
• 와 미쳤다. 내가 백준 골드 문제를 푸는 날이 오는구나.
• DFS/BFS를 코테 캠프 수업에서 학습한 후 관련 문제를 백준에서 찾아 한 번 풀어보았는데 이게 풀리네. (물론 디버깅도 오랜 시간 하면서 많이 헤맸지만)
• 다만 그래프 탐색을 한 지점이 아닌 여러 지점에서 동시에 일어난다는 것이 헷갈렸던 부분이었는데, 큐 자료구조에 그냥 순서대로 탐색 지점의 위치를 넣어주면 되는 것이었다.