[C++, 코딩테스트] 프로그래머스 : 가장 먼 노드

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector< vector<int>> graph(20001);
    vector<int> visited(20001, 0);
    queue<int> queue;
    vector<int> counts(20001, 0);

    for (vector<int> line : edge){
        graph[line[0]].push_back(line[1]);
        graph[line[1]].push_back(line[0]);
    }

    queue.push(1);
    visited[1] = 1;
    int prev = 1;
    int next = 0;
    while (queue.size() != 0){
        int num = queue.front();
        queue.pop();
        bool pass = false;
        if (prev == 0){ // 다음 더 먼 노드가 있다는 뜻이므로 값을 초기화해주고 다시 카운트 해준다.
            prev = next;
            next = 0;
            answer = 0;
        }
        prev--;
        for (int a : graph[num]){
            if (visited[a] == 0){ // 새로운 길이라면 queue에 추가해준다.
                visited[a] = 1;
                queue.push(a);
                next++;
                pass = true;
            }
        }
        if (pass == false) // 끝인 노드라면 카운트해준다.
            answer++;
    }
    return answer;
}

 

이 문제는 BFS를 사용해야하는 문제이다.

 

깊이 탐색 문제를 모면 DFS로 풀어야할지 BFS로 풀어야할지 헷갈리 때가 많다. 사실 거의 대부분의 문제가 둘 다 사용해도 되는 경우가 많다. DFS, BFS 모두 완전 탐색을 하는 경우에 사용되기는 하지만 이 문제처럼 depth(깊이)와 최단거리를 찾는 문제에서는 BFS를 이용해서 최단 거리를 체크해주는 것이 더 쉽기 때문에 BFS를 선택하게 되었다.

 

BFS는 queue를 이용해서 문제를 풀 수 있다. queue에 방문해야하는 노드를 기록하고 queue의 순서를 따라서 노드를 탐색하면 된다.

 

문제를 푸는 아이디어는 이렇다.

1. 이미 간 곳은 visited에 표시를 한다.

2. 아무데도 갈 곳이 없는 곳이 가장 멀리 있을 확률이 있다. 그래서 카운트를 해준다.

3. 만약에 다음 더 먼 노드가 발견된다면 카운트를 초기화해주고 다시 카운트해준다.

4. queue의 길이가 0이 되면 더 이상 갈 노드가 없기 때문에 종료해준다.

 

여기서 키 포인트는 깊이를 측정하는 아이디어이다. 깊이 같은 경우에는

 

깊이 1 : 처음 1번 노드가 추가한 노드 - 2 , 3

깊이 2 : 2,3번 노드가 추가한 노드 - 4, 5, 6

 

이렇게  깊이마다 추가한 노드의 개수를 기록해서 다음 깊이에 또 추가된 노드가 있는지 확인하였다.