(C++) - 백준(BOJ) 1976번 : 여행 가자

www.acmicpc.net/problem/1976

1976번: 여행 가자

floyd warshell로 푼 문제였습니다.

 

풀이방법

 1. i -> k로 갈 수 있고 k -> j로 갈 수 있다면 i -> j로도 갈 수 있기 때문에 입력받은 인접행렬을 갱신해줍니다.

 

 2. 여행코스를 확인하면서 갈수 없으면 no, 강 수 있으면 yes를 출력해줍니다. 

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,m,graph[201][201];
vector<int>course;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1,x; j <= n; j++){
            cin >> graph[i][j];
        }
        graph[i][i] = 1;
    }

    while(m--){
        int x;
        cin >> x;
        course.push_back(x);
    }
    
    sort(course.begin(),course.end());

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(graph[i][k] && graph[k][j]){
                    graph[i][j] = 1;
                }
            }
        }
    }
    int flag = 0;
    for(int i = 0; i < course.size() - 1; i++){
        if(!graph[course[i]][course[i+1]] && !graph[course[i+1]][course[i]]) flag = 1;
    }
    if(flag) cout << "NO";
    else cout << "YES";
}