[Baekjoon] 7576. 토마토

문제 바로 가기

🔍 코드

---

Reference

# 토마토


from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

q = deque()

# 큐에 맨 처음 입력받은 토마토의 위치 좌표를 append()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append((i,j))


def bfs():

    while q:
        x, y = q.popleft()

        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]

            if 0<= tx < n and 0<= ty < m and graph[tx][ty]==0:
                q.append((tx,ty))
                # 일 수를 좌표값에 저장한다.
                graph[tx][ty] = graph[x][y] + 1

# 토마토 익히기
bfs()

# 정답이 담길 변수
result = 0

# 아직도 익지 않은 토마토가 있는지 탐색
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            print(-1)
            exit(0)
        # 최댓값이 정답이다.
        result = max(result, graph[i][j])

# 처음시작을 1일에서 시작해 +1해나갔으므로 -1해준다.
print(result-1)

💫 문제 접근

---

토마토가 익을 때까지의 최소날짜를 구하고, 주변의 토마토들을 익혀나가므로 BFS를 사용해야하는 문제임을 알 수 있었다.

[잘못된 접근] 나의 첫 시도

모든 좌표를 돌면서 값이 1이면(익은 토마토이면), 해당좌표에 대해 bfs(x,y)를 실행하도록 하였다.
하지만 예제입력3에 대해서는 정답인 6이 아닌 9가 나왔다.
예제입력3에 대해 살펴보자.

내가 시도했던 방식대로라면

1. (0,0)의 주변 토마토들에 대해 조사한 뒤에
   dfs(0,0)에서 가장 큰 값은 10이므로 걸리는 시간은 9일이다. (맨 처음 익어있는 토마토에 대해 1로 시작했으므로 1을 빼주어야 한다.)
2. (3,5)의 주변 토마토에 대해 조사한다.
   dfs(3,5)를 하면 주변 토마토는 이미 익었으므로 조사하지 않는다.

가장 큰 값은 변함없이 10이므로 걸리는 시간은 9일이다.

[옳은 접근]

하지만 실제로 (0,0)과 (3,5) 주변의 토마토들은 동시에 익어간다. 잘못된 접근의 경우 (0,0)주변의 토마토들을 익힌 이후에 (3,5) 주변의 토마토들을 익힌다. (0,0)과 (3,5)이 토마토들로 연결되어 있지 않다면 상관없지만 이 둘은 연결되어 익어가며 중간에서 만난다. 따라서 동시에 익혀야 한다.

토마토들이 익어가며 중간에서 만나게 되므로 정답은 6일이 걸린다.

우선 이중 for문으로 graph의 전체를 돌면서 익은 토마토의 좌표를 큐에 삽입한다.
이렇게 하면 (0,0)주변의 토마토 조사 → (3,5)주변의 토마토 조사 번갈아 가며 토마토들을 익힐 수 있다.