[구름 IDE] 비타알고 시즌2 친구의 친구를 사랑했네(★3)

 

 

 

 

 

문제

소스코드

#include<iostream>
#include<vector>
#include<algorithm>
using graph_t = std::vector<std::vector<int>>;
using visited_t = std::vector<bool>;
using count_t = std::vector<size_t>;
/*
N: 사람의 수
E:  관계의 수
*/
int g_index;
count_t g_count;
void DFS(int started, graph_t& v, visited_t& visited) {
    visited[started] = true;
    g_count[g_index]++;
    for (const auto& values : v[started]) {
        //아직 방문하지 않은 노드라면
        if (visited[values] == false) {
             DFS(values, v, visited);
        }
    }
}
int main() {
    int N, E;
    std::cin >> N >> E;
    graph_t v(N + 1);
    visited_t visited(N + 1, false);
    g_count.assign(N + 1, 0);
    //방향 그래프
    int v1, v2;
    for (int i = 0; i < E; ++i) {
        std::cin >> v1 >> v2;
        v[v1].emplace_back(v2);
    }
    //어느 노드가 가장 많은 개수를 가졌는지 알아야 하기 때문에
    //모든 정점을 시작점으로 한다.
    for (int i = 1; i <= N; ++i) {
        g_index = i;
        visited.assign(N + 1, false);
        DFS(i, v, visited);
    }
    //가장 큰 값을 가진 반복자 리턴
    auto iter=std::max_element(g_count.begin(), g_count.end());
    //인덱스 출력
    std::cout << iter-g_count.begin();
}

 

후기

이 문제를 해결하기 위한 키워드는 DFS(Depath First Search)이다.

 

이 문제에서는 일반 DFS와 다르게 홍현이가 최대한 많은 사람에게 사랑을 나눠주기 위한 노드의 번호를 알아야 하기 때문에 입력한 모든 노드를 하나씩 탐색하면서 노드의 개수를 파악한 뒤 max_elemnet() 함수를 사용해서 가장 큰 값을 가진

빠른 번호의 사람을 리턴받아 출력하게 하였다.

 

 

이번 글부터는 티스토리에서 제공하는 코드 블록이 아닌 Color Scripter사이트에서 제공하는 기능을 사용하였다.

기존에 티스토리꺼는 줄 간격이 이상하는 등 문제도 있고 이 쪽이 좀 더 보기 좋기 때문에 변경을 진행하였다. 앞으로는

이 사이트의 기능을 사용할 예정이다.

 

출처 및 레퍼런스

위클리 비타알고 시즌2 강의 링크: https://edu.goorm.io/learn/lecture/15551/프리미엄-알고리즘-위클리-비타 알고-시즌2-입문 편

Color Scripter: https://colorscripter.com

 

* 해당 강의가 유료 전환됨으로 인해 '테스트 케이스', ' 해설 내용'은 공유하지 않고 게시하였습니다. 그래도 게시글에 문제가 있는 경우 알려주시면 수정하겠습니다.

 

관련 글

[자료구조 알고리즘/탐색 알고리즘] - 깊이 우선 탐색(Depth First Search)

[온라인 코딩/탐색(Search)] - [백준] 1260번 DFS와 BFS

[온라인 코딩/탐색(Search)] - [백준] 2606번 바이러스

[온라인 코딩/탐색(Search)] - [백준] 15649번 N과 M

[온라인 코딩/탐색(Search)] - [구름 IDE] 비타알고 시즌3 백신(★3)