[알고리즘] 백준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())
Author And Source
이 문제에 관하여([알고리즘] 백준7576), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoongja/알고리즘-백준7576저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)