가장 먼 노드 C++(그래프)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

 

문제!!

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

예시

n	times	return
6	{ {3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2} }	3

 

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

---

2. 문제풀이

그래프 문제를 많이풀지 않아서 그런지 저한테는 조금 어려웠었던 문제입니다.   처음했던 작업은 엣지가 연결된걸 편하게 보기위해 graph라는 2차원 bool타입 벡터를 만들어서 표시했습니다. 그리고 탐색은 bfs(너비 우선 탐색)를 이용하여 탐색했습니다. 넘겨줬던건 현재 들어간 거리(깊이, 카운트)로 current, 노드와 연결된 엣지상테인 graph 1번 노드와 각각의 거리를 나타낸 distance, 탐색해야하는 노드를 표시한 queue입니다. queue는 큐를 사용하지 않았고 vector를 이용해서 만들었는데 큐처럼 사용해서 저렇게 이름을 넣었습니다.   queue에 들어있는 내용만큼 노드를 탐색하고 거리를 한번도 넣지않았다면  연결된 노드를 임시큐에 넣고 거리를 넣어줍니다. 탐색이 끝날때마다 queue에서 탐색한 노드는 제외합니다.   queue에서 데이터가 모두 사라졌다면 임시큐에 있는 데이터를 queue에 넣고 bfs를 다시 재귀시킵니다.   모든탐색이 끝났다면 최대거리값을 찾아서 최대거리와 같은 거리의 노드만큼 answer를 증가시킵니다.

---

3. 소스코드

3.1 주석없는 코드

#include <vector>
#include <algorithm>
using namespace std;
 
void bfs(int current, vector<vector<bool>>& graph, vector<int>& distance, vector<int> queue) {
    vector<int> m_queue;
    while (!queue.empty()) {
        for (size_t i = 1; i < graph.size(); i++) {
            if (graph[queue[0]][i] && !distance[i]) {
                m_queue.push_back(i);
                distance[i] = current;
            }
        }
        queue.erase(queue.begin());
    }
    if (!m_queue.empty())    bfs(current + 1, graph, distance, m_queue);
}
 
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<bool>> graph(n, vector<bool>(n, false));
    vector<int> distance(n, 0);
    for (auto e : edge) {
        graph[e[0] - 1][e[1] - 1] = true;
        graph[e[1] - 1][e[0] - 1] = true;
    }
    bfs(1, graph, distance, { 0 });
    int max = *max_element(distance.begin(), distance.end());
    for (auto d : distance) {
        if (d == max)    answer++;
    }
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <algorithm>
using namespace std;
 
void bfs(int current, vector<vector<bool>>& graph, vector<int>& distance, vector<int> queue) {
    //임시큐
    vector<int> m_queue;
    //인자값으로 넘어온 큐가 빌때까지 반복
    while (!queue.empty()) {
        //연결되어있는 그래프를 확인한다.
        for (size_t i = 1; i < graph.size(); i++) {
            //큐에 들어있는 노드와 연결이 되어있어야하고, 거리설정이 안되있어야한다.
            if (graph[queue[0]][i] && !distance[i]) {
                //임시큐에 넣고 거리를 넣어준다.
                m_queue.push_back(i);
                distance[i] = current;
            }
        }
        //큐에있는 데이터 pop
        queue.erase(queue.begin());
    }
    //임시큐가 비어있지 않다면 bfs 재귀
    if (!m_queue.empty())    bfs(current + 1, graph, distance, m_queue);
}
 
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    //노드의 수만큼 2차원벡터를 만들고 1차원벡터는 false로 설정한다.
    vector<vector<bool>> graph(n, vector<bool>(n, false));
    //거리는 n개의 1차원벡터로 0으로 초기화
    vector<int> distance(n, 0);
    //연결되어 있는 엣지들은 true로 변경
    for (auto e : edge) {
        graph[e[0] - 1][e[1] - 1] = true;
        graph[e[1] - 1][e[0] - 1] = true;
    }
    //bfs함수 시작, 첫노드는 0으로 설정한다.
    bfs(1, graph, distance, { 0 });
    //최대거리를 구해서 최대거리와 같은수만큼 answer증가후 리턴
    int max = *max_element(distance.begin(), distance.end());
    for (auto d : distance) {
        if (d == max)    answer++;
    }
    return answer;
}

3.3 테스트 코드 추가

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
void bfs(int current, vector<vector<bool>>& graph, vector<int>& distance, vector<int> queue) {
    //임시큐
    vector<int> m_queue;
    //인자값으로 넘어온 큐가 빌때까지 반복
    while (!queue.empty()) {
        //연결되어있는 그래프를 확인한다.
        for (size_t i = 1; i < graph.size(); i++) {
            //큐에 들어있는 노드와 연결이 되어있어야하고, 거리설정이 안되있어야한다.
            if (graph[queue[0]][i] && !distance[i]) {
                //임시큐에 넣고 거리를 넣어준다.
                m_queue.push_back(i);
                distance[i] = current;
            }
        }
        //큐에있는 데이터 pop
        queue.erase(queue.begin());
    }
    //임시큐가 비어있지 않다면 bfs 재귀
    if (!m_queue.empty())    bfs(current + 1, graph, distance, m_queue);
}
 
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    //노드의 수만큼 2차원벡터를 만들고 1차원벡터는 false로 설정한다.
    vector<vector<bool>> graph(n, vector<bool>(n, false));
    //거리는 n개의 1차원벡터로 0으로 초기화
    vector<int> distance(n, 0);
    //연결되어 있는 엣지들은 true로 변경
    for (auto e : edge) {
        graph[e[0] - 1][e[1] - 1] = true;
        graph[e[1] - 1][e[0] - 1] = true;
    }
    //bfs함수 시작, 첫노드는 0으로 설정한다.
    bfs(1, graph, distance, { 0 });
    //최대거리를 구해서 최대거리와 같은수만큼 answer증가후 리턴
    int max = *max_element(distance.begin(), distance.end());
    for (auto d : distance) {
        if (d == max)    answer++;
    }
    return answer;
}
 
void print(int n, vector<vector<int>> edge, int answer) {
    int t = solution(n, edge);
    if (t == answer)        cout << "정답" << endl;
    else        cout << "틀림" << endl;
}
 
int main() {
    print(6, { {3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2} }, 3);
    return 0;
}

---

4. 결과