[Python/백준] 7576 토마토

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

7576번: 토마토

<문제 해설>

BFS 넓이 우선 탐색 문제이다.

1. 토마토를 담을 상자역할을 할 2차원 배열을 만든다.
2. 익은 토마토가 어디에 있는지 알기 위해 1행을 읽어서 익은 토마토의 좌표를 기록해둔다.
3. 2번에서 기록한 토마토의 좌표 모두를 좌우앞뒤로 움직여서 그곳이 0(안익은 토마토)일 경우 0을 1로 바꾼뒤 3번을 진행하면서 기록한 좌표들로 익은 토마토의  좌표를 갱신해준다. 3번이 몇번 진행 되는지도 기록해준다.
4. 새로 갱신된 좌표들로 3번을 반복(재귀)해준다.
5. 3번에서 새로 갱신된 좌표가 없다면 더 이상 익힐 토마토가 없는 것인지 어떤 경로로도 막혀 토마토를 익힐 수 없는 것인지 알아내기 위해서 모든 상자 좌표를 검사해 0이 있는지 확인한디.
6. 0이 있으면 익힐 수 없는 경우라 -1을 출력하고 0이 없다면 다 익힌 것이니 4번이 몇번 진행 됐는지(며칠이 지났는지) 출력해준다.

<예시>

예제 입력 3번

익은토마토에서 출발해서 각칸이 며칠에 채워지는지 숫자로 적어뒀다. 마지막에 익은 토마토가 6일에 익은 걸 확인할 수 있다.

예제 입력 2번

익은토마토에서 출발해도 0,0 위치에 있는 0 토마토가 -1에 막혀 익을 수 없어 -1을 출력한다.

예제 입력 5번

다익은 토마토만 있어서 0을 출력한다.

<코드>

def BFS(Tomatos):
    global day
    NewTomatos = []
    for Tomato in Tomatos:
        for mv in Move:
            y = Tomato[0] + mv[0]
            x = Tomato[1] + mv[1]
            if 0 <= y < N and 0 <= x < M:
                if Box[y][x] == 0:
                    Box[y][x] = 1
                    NewTomatos.append([y,x])
    if len(NewTomatos) == 0:
        for n in range(N):
            for m in range(M):
                if Box[n][m] == 0:
                    print(-1)
                    return
        print(day)
        return
    day += 1
    BFS(NewTomatos)

import sys
sys.setrecursionlimit(10**9)

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

Box = []
Tomatos = []
Move = [[0,1],[0,-1],[1,0],[-1,0]]
for n in range(N):
    Line = list(map(int,sys.stdin.readline().split()))
    for l in range(len(Line)):
        if Line[l] == 1:
            Tomatos.append([n,l])
    Box.append(Line)

day = 0
BFS(Tomatos)

<코드 설명>

def BFS(Tomatos): //BFS 함수 정의
    global day //며칠인지 기록할 day 전역 함수로 정의
    NewTomatos = [] //새로 기록할 토마토
    for Tomato in Tomatos: //원래 기록된 토마토마다
        for mv in Move: //앞뒤좌우로 움직여서
            y = Tomato[0] + mv[0] //움직인 좌표의 y값
            x = Tomato[1] + mv[1] //움직인 좌표의 x값
            if 0 <= y < N and 0 <= x < M: //움직인 좌표가 상자안에 있는지 확인
                if Box[y][x] == 0: //이동한 곳에 안익은 토마토가 있다면
                    Box[y][x] = 1 //안익은 토마토를 1로 교체(익히고)
                    NewTomatos.append([y,x]) //새로 좌표를 저장
    if len(NewTomatos) == 0: //새로 좌표가 저장된게 없다면 더이상 익힐 토마토가 없는 것이다
        for n in range(N): //y좌표 반복
            for m in range(M): //x좌표 반복
                if Box[n][m] == 0: //상자 안에 0이있는지 확인
                    print(-1) //있으면 익힐수가 없다는 뜻이라 -1출력
                    return //함수 종료
        print(day) //0이 없다면 며칠 걸렸는지 출력
        return //함수 종료
    day += 1 //새로 저장된 좌표가 있으니 일수 1 올려주기
    BFS(NewTomatos) //재귀함수 호출하고 새로 기록된 좌표 넘겨주기

import sys //sys 호출
sys.setrecursionlimit(10**9) //재귀 제한 해제

M, N = list(map(int,sys.stdin.readline().split())) //M,N값 받아오기

Box = [] //토마토를 담아둘 상자
Tomatos = [] //익은 토마토의 위치를 기록하는 배열
Move = [[0,1],[0,-1],[1,0],[-1,0]] //이동시킬때 편하게 사용할 배열
for n in range(N): //N만큼 반복해서
    Line = list(map(int,sys.stdin.readline().split())) //line으로 한줄씩 받기
    for l in range(len(Line)): //한줄을 한개씩 읽기
        if Line[l] == 1: //익은토마토가 있으면  
            Tomatos.append([n,l]) //좌표 기록하기
    Box.append(Line) //받은 할줄 박스에 저장

day = 0 //변수 사용 위해 0으로 초기화
BFS(Tomatos) //BFS함수 호