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

문제

친절하게도 그림이 주어져 있다. 그래프 문제임을 빠르게 캐치할 수 있다.
문제에서 추출해야 하는 정보는 다음과 같다.

• 탐색은 항상 1번 정점에서 출발한다.
• 더 이상 간선을 따라서 이동할 수 없는 경우 = 리프 노드이다.
• 1번 정점에서 리프 노드까지 팬클럽을 거치지 않고 도달하면 "yes"이다.

입출력

팬클럽 곰곰이가 존재하는 정점의 번호가 1<=s<=N임에 주의하자.

DFS로 문제를 해결해보자.

visited를 포함하는 일반적인 DFS 코드를 작성한 다음, 팬클럽 곰곰이가 위치하지 않은 경우에만 그 노드로 이동할 수 있도록 탐색 조건을 추가한다. 또한 리프 노드에 도착했다는 것은 자식 노드가 없다는 의미이므로 그 노드의 연결리스트는 비어 있음을 이용하자.

시행착오

• 팬클럽 곰곰이가 1, 즉 시작점부터 존재하는 경우에 대한 예외처리가 누락되었다.

소스 코드

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
int n, m, cnt;
bool flag;
vector<int> v[100001];
bool fan[100001];
bool visited[100001];

void DFS(int now){
    if(visited[now] || fan[now]) return; // 이미 방문한 노드 혹은 팬이 존재
    if(v[now].empty()){ // 더 이상 자식이 없음 -> 1번부터 리프까지 경로가 존재함
        flag = true;
        return;
    }
    
    visited[now] = true;
    for(int i=0; i<v[now].size(); i++){
        if(!visited[v[now][i]] && !fan[v[now][i]]){ // 방문하지 않았으면서 팬이 없는 경우에만 탐색
            DFS(v[now][i]);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
    } // 방향 그래프

    cin >> cnt;
    for(int i=0; i<cnt; i++){
        int a;
        cin >> a;
        fan[a] = true;
    } // 곰곰이 위치 표시

    DFS(1);
    if(flag) cout << "yes" << '\n';
    else cout << "Yes" << '\n';
    return 0;
}

교훈

• 그래프 문제에서 특정 노드에 조건이 부여될 경우 범위 등을 유심히 살피자.
• 그래프의 방향 존재 여부를 항상 파악하는 습관을 들이자.