[DFS/BFS] 미로 탈출

문제링크

• 이것이 코딩테스트다 연습문제

 

해설

from collections import deque

dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def is_valid_coord(x, y):
return 0 <= x < n and 0 <= y < m

def bfs(x, y):
    q = deque()
    q.append((x, y))

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

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

        if is_valid_coord(nx, ny) == False:
        	continue

        if graph[nx][ny] == 0:
        	continue

        if graph[nx][ny] == 1:
        	graph[nx][ny] = graph[x][y] + 1
            q.append((nx, ny))

    return graph[n - 1][m - 1]

print(bfs(0, 0))

 

총평/느낀점

• 항상 같은 flow로 DFS/BFS 문제를 푸는 연습을 해봐야 겠다

 

출처

• 이것이 코딩테스트다 연습문제