Algorithm | 1. BFS

알고리즘 연습을 위해 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차원