[백준] 7576번 : 토마토 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

https://www.acmicpc.net/problem/7576

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 박스 안 토마토가 다 익을 때까지의 최소 날짜를 구하는 문제이다.

만약 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지 못하는 상황이면 -1을 출력해야 한다.

보관 후 하루가 지날 때마다 익은 토마토의 인접한 익지 않은 토마토들이 익게 된다.

이렇게 익지 않은 토마토들이 익어가며 모든 토마토가 익는 최소 날짜를 구하면 된다.이는 박스 안 익은 토마토의 범위를 4방향으로 넓혀가며 모든 토마토가 익을 수 있는지 익을 수 있다면 최소 날짜를 구하는 문제이므로 너비 우선 탐색(BFS)으로 쉽게 구할 수 있다.해당 경로를 찾아나가는 것이 아니라 범위를 점점 넓혀가며 가능한 범위를 찾는 문제이기 때문에 BFS 알고리즘으로 쉽게 구할 수 있다.

 

처음에 토마토 상자의 정보를 입력받으며 익지 않은 토마토의 개수와 익은 토마토의 위치 정보를 저장한다.이후 익은 토마토의 위치를 모두 불러와 상, 하, 좌, 우, 4가지 방향으로 다음 위치를 살피며 익지 않은 토마토가 있을 경우 다음 날 익는 토마토로 해당 위치를 저장한다.모든 토마토가 익을 때까지 반복하며 날짜를 하루씩 증가시킨다.만약 모든 토마토가 익기 전, 다음 날 익는 토마토가 없으면 토마토가 모두 익지 못하는 상황이므로 -1을 출력하고 BFS 알고리즘을 종료한다.매일 익은 토마토마다 다음 날 익을 토마토의 위치를 알아야 하므로 현재 저장되어 있는 익은 토마토의 위치 기준 모두 탐색 후 다음 날 익을 토마토의 위치를 이어 탐색해야 한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. BFS 알고리즘에서 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
3. 토마토 상자의 가로 칸 수와 세로 칸 수를 입력받는다. M, N = map(int, sys.stdin.readline().split())
4. 토마토 상자의 정보를 저장할 리스트를 생성한다. box = list()
5. 익지 않은 토마토의 개수를 저장할 변수를 생성하고 초기화해 준다. blank = 0
6. 익은 토마토가 있는 위치를 저장할 deque 자료구조를 생성한다. tomato_idx = deque()
7. 토마토 상자의 세로 칸 수만큼 반복하며 for i in range(N)
   1. 각 줄마다 토마토 상자의 정보를 리스트로 입력받고 tomato = list(map(int, sys.stdin.readline().split()))
   2. 안 익은 토마토의 개수를 세어 더해준다. blank += tomato.count(0)
   3. 만약 해당 줄에 익은 토마토가 있다면 if (tomato.count(1) != 0)
      1. 토마토의 정보를 하나씩 불러오며 해당 칸이 익은 토마토일 경우 위치를 익은 토마토가 있는 위치 deque 자료구조에 추가한다. for j in range(M): if (tomato[j] == 1): tomato_idx.append([i, j])
   4. 해당 줄의 토마토 상자의 정보를 상자 정보 리스트에 추가한다. box.append(tomato)
8. 익은 토마토를 기준으로 상, 하, 좌, 우, 4가지 방향으로 매일 넓혀가기 때문에 해당 방향으로 이동할 때 좌표의 변화를 저장해 둔다. move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
9. BFS 알고리즘을 함수로 구현한다. def bfs(tomato_idx, blank, day)
   1. 일단 무한으로 반복하며 while (True)
      1. 다음 익은 토마토의 위치를 저장할 deque 자료구조를 생성한다. next_idx = deque()
      2. 현재 익은 토마토의 위치를 저장한 deque 자료구조 안의 값이 없을 때까지 반복하며 while (tomato_idx)
         1. 현재 익은 토마토의 위치를 하나씩 가져와 행과 열 변수에 저장한다. row, col = tomato_idx.popleft()
         2. 상, 하, 좌, 우, 4가지 방향으로 움직이며 for m in move
            1. 다음 행의 위치와 newRow = row + m[0]
            2. 다음 열의 위치를 구한다. newCol = col + m[1]
            3. 만약 다음 위치가 상자 안에 있고 상자 안의 다음 위치가 익지 않은 토마토의 위치이면 if (0 <= newRow < N) and (0 <= newCol < M) and (box[newRow][newCol] == 0)
               1. 해당 토마토를 익은 토마토로 변경하고 box[newRow][newCol] = 1
               2. 다음 익은 토마토의 위치 deque 자료구조에 다음 위치를 추가한다. next_idx.append([newRow, newCol])
      3. 익지 않은 토마토였다가 익은 토마토로 바뀌는 토마토의 개수를 세어 처음 익지 않은 토마토의 개수에서 빼준다. blank -= len(next_idx)
      4. 만약 익지 않은 토마토의 개수가 0개이면 if (blank == 0)
         1. 날짜를 하루 더 해주고 day += 1
         2. 무한 반복을 종료한다. break
      5. 만약 다음날 익는 토마토의 개수가 0개이면 elif (len(next_idx) == 0)
         1. 박스 안 토마토가 모두 익지 못하는 상황이므로 -1을 출력하고 print(-1)
         2. BFS 알고리즘 자체를 종료한다. return
      6. 다음 날 익는 토마토의 위치 정보를 현재 익은 토마토의 위치 정보로 옮긴다. tomato_idx = next_idx
      7. 날짜를 하루 더한다. day += 1
   2. 최종적으로 BFS 알고리즘이 종료되지 않는다면 무한 반복문 종료 후 날짜를 출력한다. print(day)
10. 만약 익지 않은 토마토의 개수가 0개이면 모든 토마토가 익어있는 상태이므로 0을 출력하고 if (blank == 0): print(0)
11. 그게 아니라면 BFS 알고리즘을 통해 모든 토마토가 익는 최소 날짜 또는 모두 익을 수 있는지를 확인한다. else: bfs(tomato_idx, blank, 0)

728x90

3. 소스코드

import sys
from collections import deque

M, N = map(int, sys.stdin.readline().split())

box = list()
blank = 0
tomato_idx = deque()
for i in range(N):
    tomato = list(map(int, sys.stdin.readline().split()))
    blank += tomato.count(0)
    if (tomato.count(1) != 0):
        for j in range(M):
            if (tomato[j] == 1):
                tomato_idx.append([i, j])
    box.append(tomato)

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]

def bfs(tomato_idx, blank, day):
    while (True):
        next_idx = deque()
    
        while (tomato_idx):
            row, col = tomato_idx.popleft()
        
            for m in move:
                newRow = row + m[0]
                newCol = col + m[1]
        
                if (0 <= newRow < N) and (0 <= newCol < M) and (box[newRow][newCol] == 0):
                    box[newRow][newCol] = 1 
                    next_idx.append([newRow, newCol])
    
        blank -= len(next_idx)
    
        if (blank == 0):
            day += 1
            break
        elif (len(next_idx) == 0):
            print(-1)
            return
    
        tomato_idx = next_idx
        day += 1

    print(day)

if (blank == 0):
    print(0)
else:
    bfs(tomato_idx, blank, 0)