[BaekJoon]백준 7576번(토마토) 풀이 in python3

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

7576번: 토마토

 

알고리즘 코딩테스트에서 단골 손님인 BFS와 DFS 문제 중 하나를 들고 왔다.

조건이 다음과 같이 있다.

1. 익은 토마도 주변(상하좌우)은 하루 사이에 익는다.
2. 애초에 모든 토마토가 익은 상태면 0을 return
3. 빈 공간으로 인해 익히지 못한 토마토가 있으면 -1을 return

 

 

다음은 코드를 보면서 하나하나 확인해보자.

 

Main 함수

import sys
import numpy as np
import collections as co

# Main
if __name__ == "__main__":
    # Read Input
    r = sys.stdin.readline
    M, N = map(int, r().strip().split())
    tomatos = np.array(list(map(int, r().strip().split())))
    for n in range(N-1):
        tmp = np.array(list(map(int, r().strip().split())))
        tomatos = np.vstack((tomatos, tmp))

    # Run
    print(BFS(M,N,tomatos))

• sys.stdin.readline VS input()
  input을 읽는 방법에는 흔히 input( )함수를 사용하는 경우가 많다.
  하지만, 다중의 입력값이 존재하고 반복적으로 읽어야하는 상황이라면 sys 모듈의 sys.stdin.readline을 추천한다.
  마치 C++의 cout과 printf와의 성능차이처럼 파이썬에서도 성능 차이를 보인다.
• strip().split()
  strip함수는 문자열 양옆의 공백을 제거해주는 함수이다. 혹시 모를 공백으로 인한 error를 방지하기 위함이다.
  split함수는 문자열을 특정 인자(default == " " : 공백) 값으로 구분하여 리스트 형태로 반환해주는 함수다.
• np.array( ), np.vstack( )
  np.array( ) 객체는 numpy의 array 객체이다. 입력값이 작거나 적은 연산을 돌릴 경우에는 일반적인 list 객체를 사용해도 좋지만, python의 가장 강점인 numpy를 사용해보았다.
  np.vstack( ) 함수는 numpy의 array 객체에 객체를 수직으로 추가하는 함수이다. list의 append 함수와 비슷하다고 보면 된다. 주의할 점은 붙여질 객체와 append할 객체를 set 형태로 묶어서 입력해주어야 한다.

BFS 함수(토마토 익히기)

# mature function
def BFS(M, N, data):
    matR, matC = np.where(data == 1)
    deq = co.deque([i,j] for i,j in zip(matR, matC))

    if M * N == len(deq) + len(np.where(data == -1)):       # 처음부터 모든 토마토가 익은 상태
        return 0

    dx = [0, 0, 1, -1]
    dy = [-1, 1, 0, 0]
    day = -1
    while deq:                  # queue가 끝날 때까지
        day += 1
        for d in range(len(deq)):
            x, y = deq.popleft()  # 익혀진 토마토
            for i in range(4):  # 상하좌우 확인 후 익히기
                nx = x + dx[i]
                ny = y + dy[i]

                if (0 <= nx < N) and (0 <= ny < M) and (data[nx, ny]) == 0:
                    data[nx, ny] = 1
                    deq.append([nx, ny])  # 새로 익혀진 토마토를 queue에 추가


    if len(np.where(tomatos == 0)[0]) > 0:            # 토마토를 모두 익히지 못한 상태
        return -1

    return day

• np.where( )
  np.where함수는 np.array 객체에서 원하는 값이 어느 위치에 존재하는지 알려주는 함수이다. 단, 특정 값이 여러 곳에 존재할 경우, x dimension은 x list로, y dimension은 y list로 반환하기 때문에 약간의 핸들링이 필요하다.
• [i, j] for i, j in zip(matR, matC)
  zip 함수를 이용하여 원하는 값이 존재하는 위치에 대한 순서쌍을 list 객체로 출력한다.
• collection.deque
  익은 토마토를 기억할 자료구조로써 queue를 사용했다. 너비 우선 탐색을 할 예정이기 때문에 새롭게 익혀진 토마토의 위치를 기억하고 이를 순차적으로 반환할 필요가 있기 때문이다.
  이 때, queue를 일반적인 list 객체로 사용해도 되긴하지만, Big-O를 생각해보면 enqueue와 dequeue가 발생할 때 O(n)이 소요되므로 비효율적이다. 이를 획기적으로 O(1)로 줄여줄 객체가 collection의 deque로 적당하다.
• dx = [0, 0, 1, -1]; dy = [-1, 1, 0, 0]
  상하좌우를 탐색하기에 좋은 스킬임에 틀림없다. 처음에 사방을 탐색할 방법으로 if(상); if(하); .. 이런 식으로 했었는데 이보다는 위의 표기법이 더 깔쌈해보인다.

 

 

로직상으로는 문제가 없고 모든 test case는 통과했지만, 왜인지 모를 이유로 실제로 제출하면 런타임 에러가 발생한다... 왜일지는 더 생각해봐야겠다...