[백준/7576] 토마토

토마토

7576번: 토마토

 

---

알고리즘 

• 일반적인 그래프 탐색과 달리, 입력된 초기 그래프에서 1이 있는 곳을 동시에 인접 지역을 탐색해야 한다. 즉, 시작점이 여러 개다.
  • 시작점을 미리 queue에 넣어서 방문할 수 있도록 한다.
• 1이 있는 지점을 방문하면서 인접 장소를 탐색한다. 이때 익지 않은 토마토가 있다면 방문하고, 몇 번째 날짜인지 기록한다.
  • 이 부분을 print로 찍어보면 다음과 같이 나온다.
  • 일단 queue에 익은 토마토(1)의 위치를 모두 append 해두었으므로, 익은 토마토(1)가 있는 곳은 순차대로 주변 탐색을 진행한다.
  • 이때 주변 탐색을 통해 익지않은 토마토(0)를 발견하면 며칠 뒤에 익을지에 대한 정보를 나의 위치의 날짜에서 1을 더해서(문제에서 주어진 조건) 저장한다.
  • 익지않은 토마토(0)인 부분의 좌표를 다음 탐색으로 저장한다.

 

 

 

전체 코드

import sys; input=sys.stdin.readline
from collections import deque

# n: 열, m: 행
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
visited = [[False]*n for _ in range(m)]
d = [(0,1),(1,0),(-1,0),(0,-1)]
q = deque()
cnt = 0

def bfs():
    while q:
        x, y = q.popleft()
        for dx, dy in d:
            nx, ny = x+dx, y+dy
            
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                if graph[nx][ny] == 0 :
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))
                    visited[nx][ny] = True
            
        for item in graph:
            print(item)
        print("==============================")

for i in range(m):
    for j in range(n):
        if graph[i][j] == 1 :
            # 익은 토마토 위치를 미리 Queue에 삽입
            q.append((i,j))

bfs()
   
ans = 0     
for i in range(m):
    for j in range(n):
        if graph[i][j] == 0 :
            print(-1)
            exit()
    ans = max(ans, max(graph[i]))

print(ans-1)

 

 

---

알게된 점

• 그래프 탐색 문제를 풀면서 미로찾기 형식(시작점이 한 곳)만 풀었었는데, 이 문제를 통해 새로운 접근을 해볼 수 있었다. 
• 문제의 양식을 보고 0인 지점을 1로 채우자, 채울 때 카운팅을 하자. 이런 풀이를 떠올렸었는데, 그래프의 지점을 하나하나 검사하는 문제가 아니므로, 날짜 계산을 그래프에 직접 반영한다는 문제해결 방식을 알 수 있었다.