백준 : 토마토 - 7576

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

예제 입력 1 

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1 

8

예제 입력 2 

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 2 

-1

예제 입력 3 

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

예제 출력 3 

6

예제 입력 4 

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

예제 출력 4 

14

예제 입력 5 

2 2
1 -1
-1 1

예제 출력 5 

0

 

 

이 문제를 읽어보면 최근 풀었던 DFS/BFS의 형식과 비슷한 형태라고 추측이 가능하다. 

 

우선 입력값으로 2차원 행렬에 대한 값을 받은 상태에서 아직 가지 않았던 곳을 시작점으로 상하좌우를 지나간 곳을 확인하도록 해야 한다. 

 

 

import sys
from collections import deque

input = sys.stdin.readline

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

queue = deque()

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

초기에는 이렇게 상하좌우로 갈 곳을 바탕으로 준비를 했다.

 

이후에는 익은 토마토를 바탕으로 시작해야 하기 때문에 익은 토마토를 찾아야 한다.

# 모든 익은 토마토를 큐에 초기화
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i, j, 0)) # 좌표와 함께 시작 날짜 0을 저장

이제 이를 바탕으로 최종적으로 모두 익게 만드는 날짜, 그리고 1인 지점부터 시작해야 하니까 시작하는 곳으로 시작하여서 각각 상하좌우 탐색 후 조건이 맞는지 확인하도록 한다.

 

이때 상하좌우 탐색 -> if 문으로 움직인 조건이 맞는지 확인하는 것은 여러번 나오니까 많이 기억하면 좋다.

final_day = 0
while queue:
    x, y, day = queue.popleft()
    final_day = day # 마지막으로 꺼낸 토마토의 날짜를 저장

    # 상하좌우 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        # 범위와 익지 않은 토마토 확인
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
            graph[nx][ny] = 1 # 방문 처리 (토마토 익음)
            queue.append((nx, ny, day + 1))

 

이때 여기서 멈추는 것이 아니라 안 익었을 경우도 있기 때문에 마지막 확인하는 조건도 첨부해준다.

# 모든 토마토가 익었는지 확인
is_all_ripe = True
for row in graph:
    if 0 in row:
        is_all_ripe = False
        break

if is_all_ripe:
    print(final_day)
else:
    print(-1)

 

<전체코드>

import sys
from collections import deque

input = sys.stdin.readline

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

queue = deque()

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

# 모든 익은 토마토를 큐에 초기화
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i, j, 0)) # 좌표와 함께 시작 날짜 0을 저장

final_day = 0
while queue:
    x, y, day = queue.popleft()
    final_day = day # 마지막으로 꺼낸 토마토의 날짜를 저장

    # 상하좌우 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        # 범위와 익지 않은 토마토 확인
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
            graph[nx][ny] = 1 # 방문 처리 (토마토 익음)
            queue.append((nx, ny, day + 1))

# 모든 토마토가 익었는지 확인
is_all_ripe = True
for row in graph:
    if 0 in row:
        is_all_ripe = False
        break

if is_all_ripe:
    print(final_day)
else:
    print(-1)