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

문제 출처 : https://www.acmicpc.net/problem/1976

문제 난이도

Gold 4

문제 접근법

플로이드-와샬 알고리즘을 사용했다.
어찌됐건 동혁이 여행 코스가 되려면 중간에 거쳐서 그 코스가 되는 것도 OK이니깐.
거쳐서 가는 것도 1로(다리가있다) 만들어줘야 겠다고 생각을 했기 때문에 이 알고리즘을 바로 생각해냈다.
-> N 범위도 삼중 포문 돌려도 되는 범위다.

주의: 자기 자신으로 가는 게 가능하다, 이 조건을 빼먹으면 1% 남기도 틀렸습니다가 뜸

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int arr[201][201];

int main() {
	int N,M;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
            if(i == j) arr[i][j] = 1;
		}
	}
	vector<int> trip;
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		trip.push_back(x-1);
	}
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][k] == 1 && arr[k][j] == 1) arr[i][j] = 1;
			}
		}
	}
	bool flag = true;
	for (int i = 0; i < trip.size()-1; i++) {
		if (arr[trip[i]][trip[i + 1]] != 1) flag = false;
	}
	if (flag) cout << "YES\n";
	else cout << "NO\n";
	return 0;
}