[알고리즘] 미로 찾기 - BFS, DFS

미로찾기를 해봅시당

https://www.youtube.com/watch?v=nyjFmDUDgO4 

코딩 빌런님의 영상을 보고 정리한 글입니다.

 

미로를 찾기위해선 두가지를 수행해야합니다.

- 미로가 처음과 끝이 이어진 길인지(목적지 까지 갈 수 있는가)

- 미로를 어떻게 최단경로로 갈 것인가

 

 

자 그럼 먼저 첫번째 부터 봅시다

1. 미로가 목적지 까지 갈 수 있는가

먼저 [0,0] 을 올라 타고 array에 [0,0] 을 넣어준다. 그 뒤 해당 좌표에는 -1 값으로 변경하고 array에서 없애줌

(갔던 길 임을 표시하는 것)

그리고 좌표를 돌면서 갈 수 있는 길인지 확인한다.

이 알고리즘대로 하면 목적지에 갈 수 있는지 알고리즘을 수행하게 됨

 

 

코드로 나타낸 것을 확인해보자

pop은 값을 반환하고 그 값을 빼낸다. 따라서 1번에서 위치에 올라가고 반환하는 것 까지 수행하게 됨

 

 

지금 포지션을 확인하면서 어레이를 업데이트하는 기능을 하는 함수이다.

 

갈 수 있는 지점인지 확인하는 함수

min,max 함수 -> 인덱스가 꼬이는 것을 방지함

 

이 알고리즘은 BFS 알고리즘임

array[0]을 꺼내면 BFS이고

array[-1]을 꺼내면 DFS가 된다고한다