[백준 7576번] 토마토 Python 파이썬 문제풀이

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

입력

M N
N줄로 토마토

 

출력

 

 

 

처음에는 굉장히 헤맸다. 어디를 기준으로 BFS를 써야하지? 라는 생각이 들어서..

하지만 여러분

제가 잘 정리했으니 글을 찬찬히 읽어보시면 도움이 될 거예요!

그럼 시작

 

 

 

풀이

 

우선 그래프 문제이고, 값이 1인 토마토에서 익은 상태가 '퍼져나가기' 때문에 BFS를 이용하면 좋겠다고 생각했다.

그러면 일수를 어떻게 구하느냐의 문제인데,

한 번 퍼져나갈 때마다 현재 값에서 +1을 해주고 graph에서 max를 찾으면 된다.

 

그림으로 살펴보자.

만약 입력으로

3 3

0 0 0

0 0 0

0 0 1

이 들어왔다면

아래처럼 표현할 수 있다.

 

3x3 graph

 

 

그럼 1을 기준으로 bfs를 돌리는거다.

이 때 찾아갈 수 있는 조건은 graph가 0이고,

visited=False일 때이다.

그리고 현재 값에서 +1을 해서 기록한다.

그러면 하루가 지난 후에는 아래와 같은 결과를 기대할 수 있다.

 

잠깐 BFS의 구현을 살펴보자.

BFS는 구현할 때 주로 아래와 같은 규칙을 따른다.

1. 현재 위치를 queue에 넣고 방문처리를 한다.
2. queue에서 하나를 꺼내고 그 주변 노드 중 방문하지 않은 노드를 queue에 넣고 방문처리를 한다.
3. queue가 빌 때까지 2를 계속한다.

 

그리고 또 하루가 지나면 아래와 같은 상황을 기대할 수 있을 것이다.

 

 

여기서 max 값을 어찌저찌 잘 가공하면 우리가 원하는 결과를 얻을 수 있다.

 

이제 대략적인 구현을 생각했다.

풀이는 크게 3가지 부분으로 나뉠 수 있을 것이다.

 

1. 입력 처리 및 세팅
2. BFS 돌려서 새로운 그래프 생성
3. 결과 처리

 

 

그렇다면 조금 디벨롭된 예시를 통해 BFS를 어떻게 돌려야할지 생각해보자.

아래와 같은 예시를 생각해보자!!

3x3 graph developed

 

1에서부터 익은 상태가 퍼져나간다.

0에만 갈 수 있고, -1은 가지 못한다.

여기서 우리는 추가되는 BFS 조건을 생각해볼 수 있다.

graph에서 0일 때만 가야겠구나!

하루가 흐르면...

 

1day after

1일이 지나면 그래프에는 2가 생긴다.

현재 상태에서 +1을 한 후에 기록해주기 때문이다.

 

2일이 흐르면 그래프에는 3이 생긴다.

 

 

3일이 흐르면 그래프에는 4가 생긴다.

이제 그래프를 다 돌았다!

그럼 결과는 몇일까? 3이다.

여기서 눈치챌 수 있는건 max 값에서 1을 빼줘야한다는 것이다.

 

 

그럼 이제 코드를 작성해보자.

아까 구상했던 풀이를 기억하는지?

 

1. 입력 처리 및 세팅
2. BFS 돌려서 새로운 그래프 생성
3. 결과 처리

 

그럼 먼저 입력처리 및 세팅 부분을 작성하자.

import sys
input = sys.stdin.readline

# 입력 처리
M, N = map(int, input().split())
graph = [[0]*M for _ in range(N)]
visited = [[False]*M for _ in range(N)]
for i in range(N):
    graph[i] = list(map(int, input().split()))

 

먼저 M, N을 받고

M, N으로 구성된 그래프와 visited 배열을 작성한다.

 

 

다음으로는 BFS를 구현할 차례이다.

그런데 알아둬야할 게 있다.

이 문제에서는 queue에 먼저 1인 숫자를 다 넣어야한다.

아까 봤던 사진 중 하나를 보면 이해가 쉬울 것이다.

 

1day after

 

(1,0)과 (2,2)의 1에서 동시에 BFS가 일어나고 있다.

그래서 나는 queue를 인자로 받는 bfs(queue)를 구현하기로 하였다.

이 queue는 처음에 1인 부분을 다 가지고 있다.

queue의 구현 방법은 아래와 같다.

 

from collections import deque
queue = deque([])
for y in range(N):
    for x in range(M):
        if graph[y][x] == 1:
            queue.append((y,x))

 

 

이제 bfs를 구현해보자.

아래와 같다.

def bfs(queue):
    while queue:
        y, x = queue.popleft()
        now = graph[y][x]
        for dy, dx in [(1,0), (-1,0), (0,1), (0,-1)]:
            ny = y + dy 
            nx = x + dx
            if (0<=ny<N and 0<=nx<M) and graph[ny][nx] == 0 and not visited[ny][nx]:
                visited[ny][nx] == True
                graph[ny][nx] = now + 1
                queue.append((ny, nx))

 

 

마지막으로 결과 처리 부분이다.

결과 처리에서 명심해야하는 점은,

1. max 값이 결과 값이 아니다.

2. 안 익은 토마토가 있는지 주의해야한다.

그래서 나는 아래와 같은 코드를 작성했다.

result = 0
max_value = 0
for i in range(N):
    if 0 in graph[i]:
        result = -1
        break
    max_value = max(max_value, max(graph[i]))
if result != -1:
    result = max_value -1
    
print(result)

 

 

모든 코드를 합쳐보면 아래와 같다!!

import sys
input = sys.stdin.readline

# 입력 처리
M, N = map(int, input().split())
graph = [[0]*M for _ in range(N)]
visited = [[False]*M for _ in range(N)]
for i in range(N):
    graph[i] = list(map(int, input().split()))
#print(graph)

from collections import deque
def bfs(queue):
    while queue:
        y, x = queue.popleft()
        now = graph[y][x]
        for dy, dx in [(1,0), (-1,0), (0,1), (0,-1)]:
            ny = y + dy 
            nx = x + dx
            if (0<=ny<N and 0<=nx<M) and graph[ny][nx] == 0 and not visited[ny][nx]:
                visited[ny][nx] == True
                graph[ny][nx] = now + 1
                queue.append((ny, nx))

queue = deque([])
for y in range(N):
    for x in range(M):
        if graph[y][x] == 1:
            queue.append((y,x))
bfs(queue)


result = 0
max_value = 0
for i in range(N):
    if 0 in graph[i]:
        result = -1
        break
    max_value = max(max_value, max(graph[i]))
if result != -1:
    result = max_value -1
    
print(result)

 

다들 화이팅!