여행 가자 (feat. 백준, 1976번)

여행 가자
https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <set>
#include <queue>
#include <vector>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M;
    bool visit[201];
    set<int> ans[201];
    cin >> N >> M;
    for(register int i = 1, j, v; i <= N; ++i)
        for(j = 1; j <= N; ++j){
            cin >> v;
            if(v == 1)
                ans[i].insert(j), ans[j].insert(i);
        }
    vector<int> route;
    for(register int m = 0, v; m < M; ++m)
        cin >> v, route.push_back(v);
    for(register int i = 0, v1, v2; i < route.size() - 1; ++i){
        bool check = false;
        v1 = route[i], v2 = route[i + 1];
        memset(visit, false, sizeof(visit));
        queue<int> q;
        q.push(v1);
        visit[v1] = true;
        while(!q.empty()){
            auto p = q.front(); q.pop();
            if(p == v2){
                check = true;
                break;
            }
            for(auto iter = ans[p].begin(); iter != ans[p].end(); ++iter)
                if(!visit[*iter])
                    visit[*iter] = true, q.push(*iter);
            }
        if(!check){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
	return 0;
}
// *&)*@*

 

반응형

1. 다익스트라를 이용하여 여행가려는 두 지점이 이어질 수 있는지를 판단하였습니다.
2. 이어질 수 없다면 이후의 곧바로 NO를 출력합니다.
3. 양쪽의 도시가 양방향이므로 결국 V1에서 V2까지 이어질 수 있는지를 판단하는 문제입니다. (V1 -> V2 사이에 어떠한 경로가 오더라도 상관없이 V1에서 V2로 갈 수 있는가 없는가 의 문제입니다.)