알고리즘: 재귀함수 (3) 응용: 미로찾기

미로찾기 조건

 

- 2차원 그리드(Grid)가 주어짐 

 

- 크기: N * N

- 입구 좌표: ( 0 , 0 )

- 출구 좌표: ( n-1, n-1 )

 

- 미로찾기 알고리즘 해결은 다양한 알고리즘이 있음. 재귀함수가 가장 적합하다는 것 같은데..?..

 

-- 내용 추가 (2021.03.16 23시 35분)

 

- 개인적으로 가장 적합한 것은 아닌 것 같음. 우선 커리큘럼상 먼저 해당 방법으로 진행된 듯한데, 스택에 담아 탐색하는 경우 모든 경우의 수를 끝까지 가서 판별하기에 속도가 느림.

 

- 반면에 BFS의 경우 큐(Queue) 자료구조로 기준점에서 물의 파동이 퍼져나가듯이 탐색함. 즉, 기준에 인접한 것에 먼저 도달하며 탐색해 나감. 그러다보니 다각도(?)로 진행되는데, 먼저 도달한 곳이 존재한다면 그 즉시 프로그램은 끝나 탐색 속도가 더 빠름.

 

sky-abraxas.tistory.com/4

알고리즘 : 너비 우선 탐색 (Breadth First Search)

 

 

 

문제 접근

 

- 현재 위치에서 출구까지 가는 경로가 있으려면

• 현재 위치가 출구이거나
• 이웃한 셀들 중 하나에서 현 위치를 다시 지나지 않고 출구까지 가는 경로가 있거나

- 미로찾기(Decision Problem) : 답이 Yes 혹은 No인 이분법 문제

 

- 반드시 중요한 것은 무한루프를 막기 위해 기존에 방문한 위치와 그렇지 않은 위치를 표시해 구분해야 함

- 접근하지 않은 좌표만 접근하며, 벽일 경우 접근하지 못함

 

문제 코드 (주석 포함)

 

https://github.com/Jeong-sky-1003/DataStructure/blob/main/src/inflearn/section2/Recursion4.java

Jeong-sky-1003/DataStructure

 

간단 메모

활용도 높은 문제에 가장 쉽다는데 코드를 안 보고 짤 수 있게 다시 복습 필수