알고리즘 연습을 위해 deque 라이브러리는 사용하지 않는다. 다만 어떻게 사용하는지는 알아두자.
1차원
1. 준비
필요한 것은 q 리스트, visited 리스트, count이다.
- q에는 현재 위치가 담겨져 있다.
- visited에는 0의 값을 가지는 리스트이고, 리스트의 크기를 설정해준다. (리스트의 크기를 잘못 설정할 시 런타임 에러가 발생할 수 있다.)
- bfs는 보통 최단거리, 최단시간을 묻는 문제이므로 시간 및 거리를 담을 수 있는 count = 0(문제에 따라 1일 경우도 있음)을 준비한다. → count를 q에 데리고 다니는 것이 포인트이다.
2. 반복
while q
로 q가 빈 queue가 될 때까지 반복한다.
반복문 내부의 구조는 다음과 같다.
- q에 담긴 node들 중에 현재 위치를 설정한다.
- 현재 count를 업데이트 한다.
- 방문한 노드를 삭제한다. (현재 위치)
- 현재 노드가 방문한 노드인가?
- 방문했으면 if문을 빠져나와 앞으로 돌아간다. 현재 노드를 업데이트 해준다.
- 방문하지 않았으면
- 방문 처리 한다.
- 찾는 노드인가? -> return count! (함수가 종료된다.)
- 아니면 q에 append한다. (문제의 조건에 따라 if문으로 처리한다. 이때 주어진 범위에 벗어나면 안된다.)
- q가 비었을 때 -1를 리턴한다. (찾지 못한 경우)
예외문제
- 가끔씩 방문처리를 하지 않아도 되는 문제가 있다. 이때 방문처리를 위한 visited 리스트를 생성하게 되면 메모리 초과가 발생한다.
A → B 문제는 방문처리를 하지 않아도 된다. 변수의 범위가 심각하게 클 경우는 이 부분을 의심해보자.
2차원