breadth first search1 BFS를 이용해 최단거리 구하기 [1] BFS(너비우선탐색) 알고리즘은 보통의 경우 tree나 graph의 노드들을 탐색하기 위해queue 자료구조를 이용해 아래와 같은 순서로 동작한다. 1. queue가 비어있는지 확인한다. 비어있으면 종료한다. 2. 비어있지 않다면 queue의 head를 pop해 현재 노드로 접근한다. 3. 현재 노드에서 이동가능한 노드들 중 아직 방문하지 않은 노드를 queue에 push한다.4. 1번으로 돌아간다. [2] 하지만 여기서 queue에 push하는 조건을 아래와 같이 바꾸면 최단 거리를 구하는데 사용할 수 있다. 현재 노드에서 방문 가능한 노드 중 아직 방문하지 않은 노드=> 현재 노드에서 방문 가능하고 (기존에 계산한 출발지에서 다음 노드까지의 거리)보다 (출발지에서 현재 노드까지의 거리 + 현재.. 2018. 6. 12. 이전 1 다음