백준 25195번 Yes or yes - C++

문제

---

 

 N$N$개의 정점과 M$M$개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.

투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.

투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.

오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 "YES or YES" 에서 다음과 같은 가사를 듣게 된다.

조금 쉽게 말하자면 넌 뭘 골라도 날 만나게 될 거야 Twice, YES or YES 가사 중 일부

 

투어리스트 곰곰이는 Twice의 노래 가사처럼, 뭘 골라도 팬클럽 곰곰이를 만나게 될 것인지 궁금해졌다.

투어리스트 곰곰이가 어떻게 이동하더라도 팬클럽 곰곰이를 만나게 된다면 "Yes" 를, 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes" 를 출력하자.

 

입력

첫째 줄에는 정점의 개수 N$N$과 간선의 개수 M$M$이 주어진다. (1≤N,M≤100000$1 \leq N, M \leq 100\,000$)

이후 M$M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 u$u$, v$v$ 가 주어진다. 이는 정점 u$u$ 에서 정점 v$v$ 로 가는 간선이 있음을 의미한다. (1≤u$1 \leq u$, v≤N$v \leq N$, u≠v$u \ne v$)

이후 M+2$M+2$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 개수 S$S$ 가 주어진다. (1≤S≤N$1 \leq S \leq N$)

이후 M+3$M+3$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호 s$s$ 가 차례대로 S$S$개 만큼 주어진다. (1≤s≤N$1 \le s \le N$)

주어진 그래프는 사이클이 없음이 보장된다. 또한 두 정점을 연결하는 간선은 최대 한 개이다.

팬클럽 곰곰이가 존재하는 정점의 번호는 중복해서 주어지지 않는다.

 

출력

문제에서 설명한 조건에 맞춰서 Yes 또는 yes 를 출력한다.

 

문제 링크

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

 

 

풀이

---

순환이 없는 그래프라고 했으니 1번부터 시작해서 팬들을 피해 더 이상 움직일 수 없을 때 까지 이동시켜보면 되는 DFS문제다. ▼

 

 

'더 이상 움직일 수 없을 때 팬을 만났는지 안만났는지 어떻게 판단하지?'

 

 

이는 flag를 계속 전달하면 된다.

1번 부터 flag를 들고 끝까지 이동을 하면 된다. ▼

 

그런데 만약에 팬을 만나게 되면 flag에 false값이 들어가게 되어 마지막에 팬을 만났는지 안만났는지를 알 수 있게 된다. ▼

중간에 팬을 만났다면 찢어진 깃발을 들고 끝까지 가게 될 것이다.

 

이렇게만 보면 정말 간단한 DFS문제다.

하지만 이렇게 풀면 시간초과가 나게 된다.

 

탐색법이 DFS인 것이지, 효율적으로 정답만 골라서 탐색하는게 아닌 전체 탐색이기 때문에 정점과 간선이 많아지면 1초내로 해결할 수 없게 된다.

 

그래서 우리는 최대한 효율적으로 탐색을 해야하는데, 가장 쉬운 방법은 flag가 false가 되면 탐색을 중지하는 것이다. ▼

 

특정 케이스에서 false가 된 flag를 끝까지 들고가봐야 결과는 변하는 것이 없다.

그렇기에 깔끔하게 그 자리에서 탐색을 중단하고 다음 것을 탐색함으로 시간을 줄일 수 있다.

 

 

C++ 코드

---

#include <iostream>
#include <vector>

using namespace std;

int N, M, S;
vector<int> G[100001];
int F[100001];
bool answer = false;

void input() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> N >> M;
  while (M--) {
    int u, v;

    cin >> u >> v;
    G[u].push_back(v);
  }
  cin >> S;
  for (int i = 0; i < S; i++) {
    int s;

    cin >> s;
    F[i] = s;
  }
}

void dfs(int node, bool meet) {
  for (int i = 0; i < S; i++) {
    if (F[i] == node) {
      return ;
    }
  }
  if (G[node].size() == 0) {
    if (meet == false) {
      answer = true;
    }
  } else {
    for (int i = 0; i < G[node].size(); i++) {
      dfs(G[node][i], meet);
    }
  }
}

void output() {
  if (answer) {
    cout << "yes" << endl;
  } else {
    cout << "Yes" << endl;
  }
}

int main() {
  input();
  dfs(1, false);
  output();
}