[99클럽/코딩테스트 챌린지/C++] "YES or yes" 문제 풀이

주어진 단방향 그래프에서 출발 정점(1번)에서 시작하여 특정 정점에 팬클럽이 있는 경우를 피할 수 없는지 여부를 확인하는 문제입니다. 출발 정점에서 가능한 모든 경로를 탐색하며, 팬클럽을 만나지 않고 종착점에 도달할 수 있는 경우 "yes"를, 그렇지 않다면 "Yes"를 출력합니다.

문제 링크 :

https://www.acmicpc.net/problem/25195

접근법

1, 그래프 초기화: 주어진 정점 수와 간선을 기반으로 단방향 그래프를 구성합니다. 또한 팬클럽이 있는 위치를 표시하기 위해 has_fanclub 배열을 초기화하여 팬클럽이 있는 정점은 2로 표시합니다.

 

2, BFS 탐색: BFS를 사용하여 출발 정점(1번)에서 이동 가능한 모든 경로를 탐색합니다. 이때, 팬클럽이 있는 정점(2)으로 이동하는 경로는 무시합니다. 이렇게 함으로써 팬클럽이 없는 경로만을 탐색할 수 있습니다.

 

3, 종착점 확인: BFS 탐색 후, 팬클럽을 만나지 않고 방문한 종착점이 있는지 확인합니다. 종착점 중 하나라도 팬클럽을 만나지 않고 도달한 경우가 있다면 "yes"를, 그렇지 않다면 모든 경로에서 팬클럽을 만나게 되는 것이므로 "Yes"를 출력합니다.

 

코드 설명 : 

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

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N + 1); // 정방향 그래프
    vector<int> has_fanclub(N + 1, false); // 팬클럽이 있는 정점을 표시

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    int S;
    cin >> S;

    for (int i = 0; i < S; i++) {
        int s;
        cin >> s;
        has_fanclub[s] = 2;
    }

    if(has_fanclub[1] == 2)
    {
        cout << "Yes" << endl;
        return 0;
    }

    // BFS 탐색을 시작하며, 방문 여부를 1로 표시합니다.
    queue<int> tour;
    tour.push(1);
    has_fanclub[1] = 1;

    while (!tour.empty()) {
        int node = tour.front();
        tour.pop();

        for (int next : graph[node]) {
            // 팬이 없는 경우에만 다음 정점으로 이동합니다.
            // => 다음 경로에 팬이 있는 경우에는 해당 경로는 필요 없으므로 무시합니다.
            if (has_fanclub[next] == 0) {
                has_fanclub[next] = 1;
                tour.push(next);
            }
        }
    }
    // 팬을 만나지 않고 도달한 종착점이 있는지 확인
    bool flag = false;
    for(int i = 1; i <= N; i++)
    {
        // 팬이 없는 경로만 탐색했을 때, 해당 정점을 방문했다면
        // 팬을 만나지 않는 경로가 존재합니다.
	    if(graph[i].size() == 0 && has_fanclub[i] == 1)
	    {
            flag = true;
	    }
    }
    if (flag == true) {
        cout << "yes";
        return 0;
    }
    cout << "Yes";

    return 0;
}

배운 점

1, BFS를 통한 조건에 따른 경로 탐색

BFS를 통해 출발 정점에서 도달할 수 있는 모든 정점을 탐색하며, 팬클럽이 있는 경로는 무시하도록 설정함으로써 조건에 맞는 경로를 탐색하는 방법을 배웠습니다. 특정 조건을 가진 정점은 탐색하지 않는 방식으로 경로를 제한할 수 있음을 이해했습니다.

2, 종착점 확인을 통한 최종 조건 판별

모든 종착점에서 팬클럽을 만나지 않은 정점이 있는지 확인하여 경로의 조건을 판별할 수 있었습니다. BFS 탐색 후, 방문 여부와 종착점을 통해 경로 조건을 확인할 수 있다는 점을 다시 한번 깨달았습니다.

결론

이 문제를 통해 탐색 경로에 특정 조건이 있을 때 조건에 맞는 정점만 탐색하는 방법을 익혔습니다. 또한, 종착점에서 특정 조건을 확인하는 방식으로 최종 결과를 도출하는 접근이 적절함을 배웠습니다. 앞으로도 그래프 문제에서 조건에 맞는 경로를 효율적으로 탐색하고 조건을 판별할 수 있을 것 같습니다.