백준 1976: 여행 가자

문제 요약

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 분리 집합

문제 풀이

DFS나 BFS로도 풀이가 가능할 것 같지만, 여기서는 유니온 파인드로 풀었다. 각 마을이 이어져 있는가로 집합으로 분류하였다.

i행 j열의 입력이 1일 경우에 i와 j번째의 노드, 즉 집합을 병합시켜 주었다. 이후 m개의 입력이 들어오는데, 문제에서는 노드를 1부터 세는 반면 나는 0부터 세고 있으므로 입력값에 -1을 해 주었다. 우선 처음 입력값의 루트 번호를 어딘가에 저장한 다음, 그 이후의 입력값의 루트 번호와 비교하여 다를 경우에 NO, 모두 같은 경우에는 YES를 출력하였다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int p[200];

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[a] += p[b];
	p[b] = a;
}

int main()
{
	int n, m, in, res = -1;
	scanf("%d%d", &n, &m);
	memset(p, -1, sizeof(int) * n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &in);
			if (in)
				merge(i, j);
		}
	}
	while (m--) {
		scanf("%d", &in);
		if (res == -1)
			res = find(in - 1);
		else {
			if (res != find(in - 1)) {
				printf("NO");
				return 0;
			}
		}
	}
	printf("YES");
	return 0;
}