(C++) 백준 1976 여행 가자 (DFS)

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

이문제의 제일 큰 함정은 같은 도시를 여러 번 방문하는 것도 가능하다. 인것같다 ;;; 처음에 이 문장 때문에 뻘짓했다.

아무튼 이 문제의 핵심은 방문하려는 도시들이 서로 연결되어 있는가 이다. 따라서 union-find와 같은 맥락으로 DFS로도 해당 문제를 해결할 수 있다.

방문하려는 도시 중 하나의 도시에 대해서만 dfs 처리하면, 도시들이 모두 연결되어 있는지 확인할 수 있다.
문제에서는 첫번째 도시에 대해 dfs처리를 하고 다른 방문하려는 도시들에 대해 isVisited이 처리되어있는지 확인해서 문제를 풀었다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N,M;
int x;
int parent[205];
int path[1005];
bool isVisited[205];

vector<vector<int>> v(205);

int main(){

    ios_base::sync_with_stdio();
    cin.tie(0);

    cin>>N>>M;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin>>x;
            if(x) {
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }

    for(int i=0; i<M; i++) cin>>path[i];

    queue<int> q;
    q.push(path[0]);

    while(!q.empty()){

        int now = q.front();
        q.pop();

        if(isVisited[now]) continue;
        isVisited[now]=true;

        for(int i=0; i<v[now].size(); i++){
            int tmp = v[now][i];
            if(isVisited[tmp]) continue;
            q.push(tmp);
        }
    }

    bool isTrue = true;
    for(int i=1; i<M; i++) if(!isVisited[path[i]]) {
        isTrue = false;
        break;
    }

    if(isTrue) cout<<"YES";
    else cout<<"NO";

}