재귀, 배열 원상복귀,

미로 - 백트래킹으로 풀기

1. 가지 치기

 맵 벗어나거나, 이미 갔던 길이나, 벽에 막히면 안감

 

bfs와 dfs 차이

가는 방법의 수를 구하라는 다 해보는 방법임. 뭘 해도 상관없음.

그러나 최단 경로는 bfs하는 것이 빠름.

 

dfs에서

모든 지점 방문 - used 지우지 않음

모든 경로 탐색 - used 지움

 

길이 존재하는지 아닌지만 알고싶다면, used = 0; 코드를 삽입하지 않으면 됨.

 

재귀의 경우 원상복구의 개념을 잘 알아야함.