PS/BOJ

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

76 2024. 1. 18. 23:48
728x90

토마토 

1 초 256 MB 177269 68852 43773 36.408%

문제

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

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

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

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 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

 

 

너비 우선 탐색(BFS : Breadth First Search)으로 풀 수 있는 문제이다.

 

BFS가 무엇인지 모른다면 아래 게시글을 참고하길 바란다.

토마토는 한 정점에서 상,하,좌,우 네 방향으로 뻗어나가서 익게 되는데 이는 그래프에서 인접정점을 방문하는것으로 해석이 가능하다.

 

문제를 해결하기 위한 아이디어는 다음과 같다.

정점의 값이 1인 토마토들을 우선적으로 BFS가 진행되어야 하고 인접정점의 값이 0일때만(익지 않은 토마토일때만) 인접 정점을 방문하도록 하여, 정점의 값을 +1씩 시켜나가며 탐색을 진행하고, 탐색이 끝난후 토마토들의 숫자중 가장 높은 숫자에서 -1을 한 값을 하면 최소 일수를 구할 수 있다.(탐색을 진행한 순번에 따라 수가 커지게 되므로)

또한 탐색이 종료된 이후, 값이 0인 정점이 존재한다면, 모든 토마토가 익지 못했다는 이야기가 되므로 문제의 조건에 맞춰 -1을 출력하면 된다.

 

코드를 보며 자세한 설명을 진행하도록 하겠다.

우선 내가 작성한 코드는 다음과 같다.

# 큐 자료구조를 쓰기 위해 덱을 import
from collections import deque

# 큐 생성
queue = deque()

# bfs를 수행하기위해 함수 정의

# 네 방향을 지정하기 위함
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph):
    global m, n
    global queue
    # 큐에 값이 존재하는동안 탐색 진행
    while queue:
        node = queue.popleft()
        x, y = node[0], node[1]
        for i in range(4):
            # 상,하,좌,우에 대해 탐색 진행
            mx = x + dx[i]
            my = y + dy[i]
            if 0 <= mx < n and 0 <= my < m:  # 영역을 벗어나지 않는지 확인
                # 안익은 토마토만 익게하면 됨(안익은 토마토는 0)
                if graph[mx][my] == 0:
                    graph[mx][my] = graph[x][y] + 1  # 토마토를 익게함
                    queue.append([mx, my])


m, n = map(int, input().split())

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

# 그래프 탐색을 진행하며 정수 1이 익은 토마토를 의미하므로,
# 하루가 지난후 익은 토마토의 영향을 받아 익은 토마토를 2로, 2 토마토에 영향을 받은 토마토를 3토마토로 증가하여 표현한다.
# 탐색 종료이후 그래프의 최대값을 출력하면, 최소일수와 관련있을것 => 단 2차원 그래프인점을 고려하여 출력
# # 탐색 종료 이후 그래프에 0인 토마토가 존재한다면 익지 않은 토마토가 있다는 의미이므로 -1을 출력하고, 그렇지 않다면 최소일수를 출력한다.

# 모든 정점을하나씩 방문하며 탐색 진행
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            # 탐색할 목록에 넣어두기 => 바로 bfs를 시행하지 않고, 날짜순으로 수행하기위해 담아만 둔다.
            queue.append([i, j])

# 1인 토마토에 대해 탐색 진행
bfs(graph)

# 안 익은 토마토(0)가 있는지 탐색하기 위함
isZero = False
minDate = 0  # 토마토가 다 익는데 걸리는 최소 일수를 기록하기 위함

# 안익은 토마토의 존재유무와 최소일수 계산
for g in graph:
    # 2차원 배열에서 한 줄 씩 검사를 실시한다 => 0인 토마토가 있는지
    if 0 in g:
        isZero = True
        break
    if minDate < max(g):
        # 최소일수를 구하기 위해
        minDate = max(g)

if isZero:
    print(-1)
else:
    # 모든 토마토가 다 익으면 최소일수를 출력한다.
    print(minDate-1)  # 마지막날짜에 +1 된 값이 들어가므로 -1을 해줌
 

BFS를 할것이므로 큐 자료구조를 사용할것이다. 따라서 큐의 역할을 할수 있는 덱 자료구조를 import하고 큐를 생성한다.

# 큐 자료구조를 쓰기 위해 덱을 import
from collections import deque

# 큐 생성
queue = deque()
 

 

문제의 조건에 따라 상,하,좌,우로 토마토가 익어가므로(이동할수 있으므로)

배열의 상,하,좌,우를 서로 간선으로 연결되어 있다고 생각한다.

 

방향을 표현하기 위한 배열로서 다음과 같이 리스트를 작성한다.

# 네 방향을 지정하기 위함
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 

이를 각 좌표에 더하면 네방향으로 표현할 수 있다. 그림으로 표현하면 다음과 같다.

 

토마토 판의 크기와 현재 토마토의 상황을 입력받는다. 이후 배열의 모든 인덱스를 순환하며, 인덱스의 값이 1과 같다면, 큐에 삽입한다.

이렇게 삽입된 데이터를 바탕으로 BFS를 진행한다.

m, n = map(int, input().split())

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

# 모든 정점을하나씩 방문하며 탐색 진행
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            # 탐색할 목록에 넣어두기 => 바로 bfs를 시행하지 않고, 날짜순으로 수행하기위해 담아만 둔다.
            queue.append([i, j])

# 1인 토마토에 대해 탐색 진행
bfs(graph)
 

BFS에 대한 코드는 다음과 같다.

네 방향으로 이동시 영역을 벗어나는지 확인해야 하므로 전역변수로 m,n을 이용하고, 큐에 데이터를 삽입해야 하므로 생성한 큐를 전역변수로 사용하기 위해 global 키워드를 이용한다.

큐에 데이터가 존재하는 동안 탐색을 진행하며, 큐에서 정점을 뽑아 상하좌우로 방문하고 해당 정점이 그래프의 영역(배열의 영역)을 벗어나지 않고 0이라면(아직 안 익은 토마토라면)방문한다.

def bfs(graph):
    global m, n
    global queue
    # 큐에 값이 존재하는동안 탐색 진행
    while queue:
        node = queue.popleft()
        x, y = node[0], node[1]
        for i in range(4):
            # 상,하,좌,우에 대해 탐색 진행
            mx = x + dx[i]
            my = y + dy[i]
            if 0 <= mx < n and 0 <= my < m:  # 영역을 벗어나지 않는지 확인
                # 안익은 토마토만 익게하면 됨(안익은 토마토는 0)
                if graph[mx][my] == 0:
                    graph[mx][my] = graph[x][y] + 1  # 토마토를 익게함
                    queue.append([mx, my])
 

배열의 값이 1인 정점들을 큐에 우선적으로 삽입함으로서, 하나의 정점에서 계속해서 탐색을 이어나가지 않고, 각 정점에서 순차적으로 값이 뻗어나갈수 있게 된다.

 

탐색이 종료된 이후, 배열의 각 정점에 대해서 0인 값이 존재하는지 확인하고 0인 값이 존재한다면 안 익은 토마토가 존재한다는것이므로 최소일수 계산을 중단한다.

0인 값이 존재하지 않는다면, 배열의 각 요소에 대해서 최대값을 계산하고, 출력할때는 -1을 한다.(1일차부터 2로 계산되므로)

# 안익은 토마토의 존재유무와 최소일수 계산
for g in graph:
    # 2차원 배열에서 한 줄 씩 검사를 실시한다 => 0인 토마토가 있는지
    if 0 in g:
        isZero = True
        break
    if minDate < max(g):
        # 최소일수를 구하기 위해
        minDate = max(g)

if isZero:
    print(-1)
else:
    # 모든 토마토가 다 익으면 최소일수를 출력한다.
    print(minDate-1)  # 마지막날짜에 +1 된 값이 들어가므로 -1을 해줌