[백준 파이썬] # 7576 토마토

Silver I

# 7576 토마토

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

7576번: 토마토

 

풀이

M, N = map(int, input().split())
house = [list(map(int,input().split())) for i in range (N)]

from collections import deque

def bfs(graph):
    queue = deque()

    # key_iea
    for x in range(M):
        for y in range(N):
            if house[y][x] == 1:
                queue.append((x, y))

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

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<M and 0<=ny<N:
                if house[ny][nx] == 0:
                    queue.append((nx, ny))
                    house[ny][nx] = house[y][x] + 1

    return graph

li = []

for i in bfs(house):
    if 0 in i:
        li.append(-1)
    else:
        li.append(max(i))

if 0 in li:
    print(-1)
else:
    print(max(li)-1)

 

풀이 방법

# key_idea 설명

• while 구문을 반복 하기전 house 전체를 탐색해서 1이 있는지 확인한다
• 1을 발견했을 때 queue에 해당 인덱스를 append 한다

→ 큐 구문의 경우 append 해준 순서에 따라 진행되기 때문에, # key_idea를 적용하면 1을 가진 인덱스를 번갈아가며 진행

 

 

ex) 예제 3 적용 예시

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

• 1은 house[0][0], house[3][5]에 있다

 

• key_idea를 적용하지 않으면 가장 먼저 탐색되는 house[0][0]에서 bfs가 시작될 뿐 house[3][5]의 1은 적용되지 않는다 (다음과 같이 한쪽 방향에서만 탐색이 진행되었다)

[[1, -1, 7, 8, 9, 10],
 [2, -1, 6, 7, 8, 9],
 [3, 4, 5, 6, -1, 10],
 [4, 5, 6, 7, -1, 1]]

 

• 반면 1이 존재하는 인덱스를 큐에 먼저 삽입하고 진행했을 때 양 방향에서 탐색하는 모습을 볼 수 있었다

[[1, -1, 7, 6, 5, 4],
 [2, -1, 6, 5, 4, 3],
 [3, 4, 5, 6, -1, 2],
 [4, 5, 6, 7, -1, 1]]

 

후기

• 큐 구조가 갖는 이점을 조금 이해할 수 있었다 : 양방향에서 순차적인 탐색이 가능
• 혼자였으면 끙끙대고 힘들어했겠지..만 스마트한 스터디원이 있어서 참 다행이다
• 알고리즘 풀이를 스터디로 하길 잘했다 생각이 들었다