BOJ (C/C++) 1976번: 여행 가자

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

---

풀이

여행 경로를 각각 하나의 출발지-도착지로 봐서 모든 출발지에서의 값을 구할 수 있는 프림 알고리즘을 사용함.문제에서 보면 city[i][i]=0으로 되어 있는데 같은 도시에서 출발 도착은 가능하므로 이를 1로 바꿔줘야 한다.

---

코드

#include <stdio.h>
#include <vector>
using namespace std;

int main() {
	bool city[201][201] = { 0, };
	vector <int> plan;
	int N, M, n;

	// input
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++)
			scanf("%d", &city[i][j]);
	}
	for (int i = 0; i < M; i++) {
		scanf("%d", &n);
		plan.push_back(n);
	}

	//Prim
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			city[i][i] = true;
			for (int j = 1; j <= N; j++) {
				if (city[i][j]) continue;
				if (city[i][k] && city[k][j]) city[i][j] = true;
			}
		}
	}

	// Find
	for (int i = 0; i < M - 1; i++) {
		int s = plan[i], e = plan[i + 1];
		if (!city[s][e]) {
			printf("NO\n");
			return 0;
		}
	}

	printf("YES\n");
	return 0;
}