[Baekjoon] 1976번: 여행 가자

 

 

 

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

1976번: 여행 가자

 

---

 

문제 해결 과정

착안

도시들이 각각 서로 다른 번호로 구분되고(정수형 데이터), 도시들 사이의 연결 여부가 문제에서 주어지고 있으며 여행 경로에 해당하는 도시를 방문하기 위해 다른 도시를 중복으로 방문이 가능하다. 여행 경로가 주어졌을 때 시작 도시에서 경로 내에 있는 도시들을 방문이 가능한지의 여부만 확인하면 되는 문제이므로, 트리 또는 그래프의 구조를 활용해 탐색을 빠르게 수행하는 것을 목표로 문제를 해결하고자 하였다.

 

시작 도시를 $A$ 도시라고 하고, 여행 경로 상에 있는 다른 도시들 중의 하나를 $B$ 도시라고 하면, 시작 도시인 $A$로부터 $B$까지 어떠한 경로를 통해서든 연결이 되어있다면 '이동 가능한 도시', 연결이 되어있지 않다면 '이동 불가능한 도시' 의 두 가지 집합으로 구분을 지을 수 있다. 두 집합은 반드시 교집합이 없으므로 이는 곧 서로소 집합 구조(분리 집합 구조, disjoint set)로 문제의 상황을 나타낼 수 있다는 의미이다. 따라서 서로소 집합 구조를 사용하여 $B$가 $A$를 최상위 부모로 하는 집합 내에 포함되어있는지 여부를 판단하여 빠르게 경로 연결 여부를 탐색하고자 하였다.

 

구현

1부터 최대 200 까지의 도시의 번호에 따라 해당 번호의 도시에 대한 집합 포함 여부를 나타내기 위해 부모를 가리키는 값을 저장할 배열을 선언하여 사용하였다(편의상 전역변수로 선언, Sets). 각각 $N$ 개의 도시에 대해 $i$ 번째 도시가 $j$ 번째 도시와 연결된 여부가 0과 1로 주어질 때 연결 여부가 1(true)이면 유니온 연산을 통해 $i$ 번째 도시와 $j$ 번째 도시를 같은 집합으로 포함(유니온, union)을 시키는 과정을 수행했다.

 

한편, 마지막으로 주어지는 여행 경로를 입력받았을 때 시작 도시로부터 연결이 되어있는지 판단하는 문제의 특성을 활용해 시작 도시가 속한 집합의 최상위 부모와, 각각 주어지는 도시들의 최상위 부모가 같은지 판단(파인드, find)하여 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int* Sets = new int[201];

int Find(int a)
{
	if (a == Sets[a])
		return a;

	return Sets[a] = Find(Sets[a]);
}

void Union(int a, int b)
{
	if (a == b)
		return;

	int pa = Find(a);
	int pb = Find(b);
	if (pa == pb)
		return;

	Sets[pb] = a;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M, Start, City;
	bool Connected;
	cin >> N >> M;

	for (int i = 0; i <= N; i++)
		Sets[i] = i;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> Connected;
			if (Connected)
				Union(i, j);
		}
	}

	cin >> Start;
	Start = Find(Start);
	M--;
	while (M--)
	{
		cin >> City;
		
		if (Start != Find(City))
		{
			cout << "NO" << "\n";
			return 0;
		}
	}

	cout << "YES" << "\n";
	delete[] Sets;
	return 0;
}

 

실행 결과