[백준/BOJ] 7576번 : 토마토 _Python

7576번: 토마토

 

>문제

>접근방법

   감이 상하좌우의 감을 익히기 때문에 깊이우선탐색을 사용한다. 하루가 지날 때마다 감이 있는 위치에 1을 더해준다. bfs가 끝났을 때 가장 큰 숫자가 토마토가 모두 익을 때까지의 최소 날짜이다.

 

 

>풀이법

   1. 2차원 리스트 box 생성 후 상자에 담긴 토마토들의 정보를 입력받는다.

   2. 상자 중에서 1이 담긴 모든 위치를 큐에 삽입한다. (이때 좌표를 입력받으므로 큐의 요소는 리스트([])로 생성한다)

   3. 큐의 원소를 꺼내 좌표를 a와 b에 담고 box[a, b]를 기준으로 상하좌우의 원소에 box[a, b]+1을 누적시켜준다.

   4. 상하좌우는 dx = [-1, 1, 0, 0] 와 dy = [0, 0, -1, 1] 을 이용해서 탐색한다.

   5. 이때 상하좌우의 값은 박스 내의 숫자여야 하고 토마토가 익지 않은 상태(0)여야 한다.

   6. box에 0이 하나라도 있으면 -1을 출력하고, 모두 익었으면 요소의 최대값 - 1을 출력해준다. (초기값이 익은 감(1)이었기 때문)

 

 

>코드

from collections import deque
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def bfs() :
    while queue:
        a, b = queue.popleft()

        for l in range(4):
            nx, ny = a + dx[l], b + dy[l]

            if 0 <= nx < c and 0 <= ny < r and box[nx][ny] == 0:
                box[nx][ny] = box[a][b] + 1
                queue.append([nx, ny])

## main
r, c = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(c)]
queue = deque([])
count = 0

for i in range(c): # 세로
    for j in range(r): # 가로
        if box[i][j] == 1:
            queue.append([i, j])

## 출력
bfs()
for i in box:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    count = max(count, max(i))
print(count - 1)

 

 

>결과

 

 

>결론 

dx, dy는 또 처음 써보네 골드 너무 어려워

탁이 때문에 의자 쪼금밖에 못 앉아서 궁둥이 아파