[알고리즘] 백준7576

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

dfs/bfs 부시기 3일차

문제를 풀어나간 순서 :
1. 토마토 익은 걸 표현했지만, 기본적인 미로찾기 문제와 같다.
2.기본적인 bfs 알고리즘을 먼저 구현하고 , 예외처리를 하자!

from collections import deque

m,n = map(int,input().split())
queue = deque()

arr = []
for _ in range(n):
    arr.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 :
            queue.append((i,j)) #익은 토마토 넣어주기

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

def dfs():
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx <= -1 or nx >= n or ny <= -1 or ny >= m:
                continue
            if arr[nx][ny] == -1 :
                continue
            if arr[nx][ny] == 0 :
                queue.append((nx,ny))
                arr[nx][ny] = arr[x][y] + 1

    result = max(map(max,arr)) - 1 #map 이용해서 이차원 배열 max값

    br = False
    
    for row in arr :
        for col in row :
            if col == 0:
                result = -1
                br = True #이중포문 빠져나가기 위해 
                break
        if br == True:
            break
       
    return result
    

print(dfs())

좋은 웹페이지 즐겨찾기