문제

문제 해석

같은 도시를 여러 번 방문해도 되기 때문에, 여행 경로에 포함된 도시들이 어떤 방식으로든 연결만 되있으면 여행 계획은 무조건 달성할 수 있다.

따라서 여행 계획에 포함된 도시들이 연결된 상태인지를 확인하면 된다.

그리고 이러한 set을 유지하기 위해서는 disjoint set이 적절하다.

알고리즘

자료구조

• disjoint set

결과

/*
DFS
*/
#include <iostream>
#include <vector>

using namespace std;

const int MAX_CITY = 200;

int N; // num of city
int M; // num of city to travel

vector<vector<int>> adjList(MAX_CITY);
vector<bool> bVisited(MAX_CITY, false);

void DFS( int n )
{
    if ( bVisited[n] == true )
        return;

    bVisited[n] = true;

    for ( size_t i = 0; i < adjList[n].size(); i++ ){
        DFS(adjList[n][i]);
    }
}

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N;
    cin >> M;
    for ( int r = 0;  r < N; r++ ){
        for ( int c = 0; c < N; c++ ){
            int in;
            cin >> in;
            if ( in == 1 ){
                adjList[r].push_back(c);
            }
        }
    }

    int c;
    cin >> c;
    DFS(c-1);
    for ( int i = 1; i < M; i++ ){
        cin >> c;
        if ( bVisited[c-1] == false ){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";

    return 0;
}

Other