[구름 IDE] 비타알고 시즌2 졸업(★3)

 

 

 

 

 

문제

소스코드

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
 
using NODE = std::vector<std::vector<int>>;
std::vector<bool>   g_visited;
 
void DFS(NODE& n,int S) {
    int weight=1;
    std::stack<int> s;
    s.emplace(S);
 
    while (s.empty() == false) {
        auto topVaule = s.top();
        s.pop();
        g_visited[topVaule] = true;
 
        for (const auto& node : n[topVaule]) {
            if (g_visited[node] == false) {
                ++weight;
                s.emplace(node);
            }
        }
    }
    std::cout << weight << "\n";
}
 
int main() {
    //N 과목의 수, M 관계의 수 , 졸업하기 위해 들어야하는 과목 C
    int N, M, C;
    std::cin >> N >> M;
    NODE n(N + 1);
    g_visited.assign(N + 1, false);
 
    int s{}, e{};
    for (int i = 0; i < M; ++i) {
        // s start, e end
        std::cin >> s >> e;
        //Reverse
        n[e].emplace_back(s);
    }
    std::cin >> C;
    DFS(n, C);
}

후기

이 문제를 해결하기 위한 키워드는 BFS/DFS이다.

 

BFS로도 충분히 풀 수 있으며 나는 DFS에 Stack을 이용해서 풀었다. 재귀로는 뭔가 헷갈리는 느낌이 있어서 익숙한

Stack을 이용해서 풀었다.

좀 특이한거는 여러가지 케이스가 생길 수 있어서 노드의 간선을 뒤집어서 풀어야 한다는 도움을 받아서 풀 수 있었다.

 

자세한 알고리즘 설명은 관련 글에 정리하였다.

 

출처 및 레퍼런스

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

 

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

 

관련 글

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

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

[온라인 코딩/탐색(Search)] - [구름 IDE] 비타알고 시즌2 친구의 친구를 사랑했네(★3)

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