[백준]_7576번 : 토마토(파이썬)

7576번: 토마토

다행히도 이 문제를 풀기 하루 전에 'Z', '유기농 배추', '쉬운 최단거리'와 같은 그래프 탐색 문제를 많이 풀어 단련이 되어 있는 상태로 푼 문제라 그런가 첫 번째 시도만에 초록색 "맞았습니다!!"를 띄워서 너무 기뻤다. 이번 해설에서는 기쁜 마음과 더불어 문제를 자세히 해설해 보겠다. 필자 또한 그래프 탐색 문제의 열쇠를 알기 전에 어떤 부분들이 이해가 안 되었는지를 중심으로 서술하고자 한다. 물론 이 분야를 다 깨우쳤다는 뜻은 절대 아니다;;

---

사용 도구들과 사고

먼저 문제 풀이에 앞서 우리가 중요하게 생각해야 될 조건들을 찾아보자. 그렇면 아래와 같이 정리할 수 있다.

• 익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 들어가지 않는 칸, 즉 장애물은 -1로 입력한다.
• 익은 토마토가 인근 토마토에 줄 수 있는 영향(익음)은 상하좌우 4방향 뿐이다. 즉 대각선은 불가능하다.

위의 조건들이 문제 풀이에 있어 가장 중요한 기저(basis)들이다. 아무리 코딩을 잘한다고 한들 조건을 잘못 알고 있으면 무용지물이기 때문이다.

 

이제 어떤 방식으로 답을 구해낼 것인지 생각해 보자. 일단 어떤 방식으로 접근하든 간에 사용자가 입력한 농장을 2차원 배열로 저장해야 함을 알 수 있다. farm이라는 2차원 배열에 담기로 하자.

farm에 존재하는 1들의 위치 정보를 따로 취득한 뒤 너비 탐색의 기본적인 아이디어를 사용해 주면서 1 주변의 상하좌우 4칸들에 1을 더해주면서 영역을 확장해 주자. 여기서 너비 탐색의 기본적인 아이디어는 아래 더 보기 글을 확인해 주기를 바란다.

먼저 deque를 collections에서 import 하는 것으로 시작한다. 이제부터 q=deque([ ])를 생성해 준다. 그 후 처음 시작하는 위치(이 문제의 경우 1의 정보) 정보를 q에 append 해준다. 이를테면 행과 열의 정보가 되겠다.

 

이제부터 q가 비어 있을 때까지 다음 단계들을 반복해 준다.

1. q에 담긴 정보를 popleft해서 특정 변수에 따로 저장해준다.
2. 뽑아낸 위치 정보의 위치를 토대로 그래프(우리의 경우는 farm) 주변을 검사해준다. 만약 특정 조건을 만족시킨다면(더 탐색할 가치가 있는 위치라면) q에 그 새로운 위치 정보를 대입해준다. 즉 그래프 탐색은 아직 끝나지 않았다. 왜냐하면 아직 q가 채워져 있기 때문이다. 그래서 가장 겉에 있는 반복문으로 while q를 사용한다.
3. 또한 방문한 노드(위치)를 방문했다고 저장해준다. 이 문제의 경우 visited라는 farm크기의 2차원 배열을 전부 0으로 초기화 하고 방문한 노드들만 1로 바꿔줄 것이다. 그리고 방문한 노드는 다시 탐색하지 않는다. 즉 2번 과정에서 q에 다시 정보를 append하는 일은 없도록 한다.
4. q가 비어 있을 때 까지 위의 과정을 반복해준다.

먼저 정답 코드를 보면서 설명을 이어나가겠다.

시도 1(Python)

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

# m행 n열
n, m = map(int, input().split())
farm = []
visited = [[0] * n for _ in range(m)]
q = deque([])
# 입력
for i in range(m):
    ls = [*map(int, input().split())]
    farm.append(ls)
# 1 위치 추출, 0으로 만들기
for i in range(m):
    for j in range(n):
        if farm[i][j] == 1:
            q.append([i, j])
            farm[i][j] = 0
            visited[i][j] = 1
# 탐색
while q:
    r, c = q.popleft()
    for rr, cc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= r + rr < m and 0 <= c + cc < n and farm[r + rr][c + cc] == 0 and visited[r + rr][c + cc] == 0:
            q.append([r + rr, c + cc])
            farm[r + rr][c + cc] = farm[r][c] + 1
            visited[r + rr][c + cc] = 1
# 최댓값 추출 또는 추출 불가인지 확인
out = 0
ans = 0
for r in range(m):
    for c in range(n):
        if visited[r][c] == 0 and farm[r][c] != -1:
            out = 1
            break
        if ans < farm[r][c]:
            ans = farm[r][c]
# 출력
if out:
    print(-1)
else:
    print(ans)

<해석>

 

# 입력

farm의 정보들을 입력받는다.

 

# 1 위치 추출, 0으로 만들기

1의 위치 정보들을 q에 추가해주는 동시에 visited에도 넣어 준다. 만약 미리 visited에 넣어주지 않으면 나중에 탐색할 때(-1이 아닌 지점들만 탐색할 것이기 때문에) 기존에 존재했던 1의 위치에 접근해서 데이터들을 망가트릴 수 있기 때문이다. 기존 1의 위치에는 0이 대입되어야 한다. 왜냐하면 각각의 토마토 자리에 저장되는 숫자들은 며칠 후에 익을 것인지 알려주는 값이 저장될 것이기 때문이다. 즉 애초에 존재하는 토마토에는 0이 대입되어야 한다.

 

#  탐색

bfs와 q를 이용하여 farm 전체를 구석구석 탐색해 준다. 물론 반드시 탐색한 위치의 정보는 visited와 farm에 갱신해 준다.

 

# 최댓값 추출 또는 추출 불가인지 확인

farm 전체를 검사해 주면서 visited에 갱신되지 않은(0) 좌표인 동시에 그 좌표에 존재하는 값이 -1이 아닌지 확인해준다.

 

# 출력

출력!

 

물론 아직 들 수 있는 의문 중 하나는 초기에 1이 여러 개 존재할 때 누구를 먼저 q에 대입해 주는 것이 중요하지 않을까 생각할 수도 있다. 하지만 누구부터 시작하든 farm의 최종 결과는 바뀌지 않음을 알 수 있다. 직접 출력해 보면 알 수 있는 사실이다!!