BOJ - 여행 가자(1976)

경로를 찾는 문제처럼 보이지만, 유니온 파인드(Union-Find)를 사용해서 해결할 수 있는 간단한 문제입니다. 입력으로 들어온 각 두 도시를 연결 하고, 마지막 입력으로 주어진 도시들이 모두 연결되어 있는지 확인하는 문제입니다. 주어진 도시들의 root 가 모두 같으면 하나의 그래프로 연결되어 있다고 볼 수 있습니다.

[A-B], [B-C], [A-D] 이면 A, B, C, D 는 모두 하나의 그래프로 이루어져 있습니다.

유니온 파인드

#define MAX 
int parent[201];
int find(int n) {
	if (parent[n] == 0) return n;
	else {
		int p = find(parent[n]);
		parent[n] = p;
		return p;
	}
}

void merge(int a, int b) {
	int ap = find(a);
	int bp = find(b);
	if (ap == bp) return;
	parent[bp] = ap;
}

메인 함수

#include <stdio.h>
int main() {

	int N, M;
	scanf("%d %d", &N, &M);

	// input
	int isConn;
	for (int a = 1; a <= N; a++) {
		for (int b = 1; b <= N; b++) {
			scanf("%d", &isConn);
			if (isConn == 1) {
				merge(a, b);
			}
		}
	}

	// check if root same
	int n, np, prevnp, isYES;
	for (int i = 0; i < M; i++) {
		scanf("%d", &n);
		// find root
		np = find(n);
		if (i > 0) {
			// check if roots same
			isYES = (prevnp == np);
			if (isYES == 0)
				break;
		}
		prevnp = np;
	}

	
	// output
	if (isYES) {
		printf("YES\n");
	} else {
		printf("NO\n");
	}
	return 0;
}