[Algorithm] 백준 7576 Python

Serin Yoon·2021년 3월 9일
1

Algorithm

목록 보기
7/7
post-thumbnail

백준 7576번 - 토마토

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


접근 방식

  • 너비 우선 탐색 (하루에 한 번 인접 토마토가 익기 때문)
  • 너비 우선 탐색은 재귀 호출을 사용하지 않고, 큐와 while문을 사용
    (BFS를 자꾸 재귀 호출 함수로 구현하려고 해서 삽질을 했다!)

전체 코드

import sys
from collections import deque

input = sys.stdin.readline

def BFS():
    day = 0
    
    #큐에 탐색해야 하는 노드 없을 때까지 실행
    while queue:
    
        day += 1 #일수 증가
        
        #큐에 있는 노드 수만큼 탐색
        for _ in range(len(queue)):
        
            x, y = queue.popleft() #큐에 있는(탐색해야 하는) 노드의 좌표
            
            for i in range(4):
                pointX = x + dx[i] #상하좌우
                pointY = y + dy[i] #상하좌우

                #인덱스 벗어나지 않는 경우
                if -1 < pointX < N and -1 < pointY < M:
                
                    #아직 방문하지 않은 경우 (익지 않은 토마토)
                    if paint[pointX][pointY] == 0:
                        paint[pointX][pointY] = 1 #익음 (방문처리)
                        queue.append([pointX, pointY]) #큐에 삽입

    #익지 않은 토마토 남아있는 경우 -1 반환
    for i in range(len(paint)):
        for j in range(len(paint[i])):
            if paint[i][j] == 0:
                return -1

    #모두 익은 경우 일수 출력
    return day - 1

M, N = map(int, input().split())

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

queue = deque([])

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for i in range(len(paint)):
    for j in range(len(paint[i])):
        if paint[i][j] == 1:
            queue.append([i, j])

print(BFS())

익은 토마토는 1, 익지 않은 토마토는 0로 표현된다.
(토마토가 없는 자리는 -1이므로 신경쓰지 않는다.)

따라서 방문 처리를 위한 배열을 별도로 생성할 필요가 없고, 상하좌우의 노드의 값을 확인하고, 만약 0인 경우 아직 방문되지 않은 토마토이므로 값을 1로 바꿔주면 방문처리가 된다.

상하좌우 노드를 탐색하는 방법은 이전 글에 작성해놓았다.
https://velog.io/@serinyoon/Algorithm-파이썬-델타-이용해-상하좌우-탐색하기

profile
티스토리로 이사했습니다 🏠

0개의 댓글