백준 1976 여행 가자 혼내주기

 

플로이드 와샬로 도시끼리 연결되어 있는지 확인하면 된다. 여행 경로가 A-A와 같이 자기 자신으로 가는 경우를 처리해주지 않아서 조금 헤맸다. 

 

혹시 이 문제로 삽질하고 있다면 여행 계획으로 들어오는 숫자가 1부터 시작한다는 것을 놓치고 있진 않은지 확인하자.

 

풀고 보니 대부분의 사람들이 유니온 파인드를 이용해 풀었다. 추후에 유니온 파인드를 공부한 뒤 다시 풀어볼 예정이다.

 

#include <iostream>
using namespace std;

int map[200][200], arr[1000];

int main(){

    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin >> map[i][j];

    for(int i = 0; i < n; ++i)
        map[i][i] = 1;
    
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                if(map[i][k] && map[k][j]) map[i][j] = map[j][i] = 1;

    for(int i = 0; i < m; ++i)
        cin >> arr[i];

    for(int i = 0; i < m-1; ++i){
        if(!map[arr[i]-1][arr[i+1]-1]){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";

    
}