그림과 같은 그래프를 대상으로 다음 알고리즘을 적용하였을 때, 결과에 … | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지

그림과 같은 그래프를 대상으로 다음 알고리즘을 적용하였을 때, 결과에 대한 설명으로 옳지 않은 것은? (단, 탐색의 시작 정점은 1이고, Q는 큐 객체이며, Q.enqueue()와 Q.dequeue()는 큐 Q에 대한 삽입과 삭제 연산이고, 각 정점의 방문을 표시하는 것은 visited[] 배열을 이용한다)
_FS(v) {
    visited[v] <- YES;        // 정점 v에 대한 방문 표시
    Q.enqueue(v)
    while(!Q.empty()) {       // Q가 비어있지 않은 동안
        w <- Q.dequeue();
        for all u ∈ (w에 인접한 정점) {
            if(visited[u] != YES) {
                visited[u] <- YES;
                Q.enqueue(u);
            }
        }
    }
}

알고리즘의 수행에 따른 노드의 방문 순서는 1 → 2 → 5 → 9 → 8 → 4 → 7 → 6 → 3이다.

너비 우선 탐색(BFS, Breadth First Search) 알고리즘이다.

시작 정점으로부터 가까운 정점들을 먼저 방문하고 멀리 떨어져 있는 정점들을 나중에 방문하는 탐색방법이다.

알고리즘은 그래프의 모든 정점을 방문한다.

방문 순서가 1 → 2 → 5 → 9 → 8 → 4 → 7 → 6 → 3이라는 설명이 옳지 않다.
제시된 알고리즘은 큐에 정점을 넣고 꺼내며 인접 정점을 차례로 방문하는 너비 우선 탐색이다. 정점 1을 꺼낼 때 인접 정점 2, 3, 4가 모두 먼저 방문되므로 그 뒤에야 5, 6, 7, 8, 9가 방문된다(번호가 작은 인접 정점부터 넣으면 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9).
2 다음에 바로 5로 내려가는 순서는 한 경로를 끝까지 파고드는 깊이 우선 탐색의 방문 순서이다.
너비 우선 탐색 알고리즘이라는 설명: 큐(FIFO)를 사용하므로 옳다.
가까운 정점을 먼저, 먼 정점을 나중에 방문한다는 설명: 시작 정점으로부터의 거리 순으로 방문하는 BFS의 특징이다.
모든 정점을 방문한다는 설명: 그래프가 연결되어 있어 시작 정점 1에서 모든 정점에 도달한다.