[BOJ/백준 1976/C++] 여행 가자

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

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라는 여행경로를 통해 목적을 달성할 수 있다.

- 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하라.

 

[문제 조건]

- 첫 줄에 도시의 수 N이 주어진다. ( 1 ≤ N ≤ 200 )

- 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. ( 1 ≤ M ≤ 1000 )

- 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다.

- 마지막 줄에는 여행 계획이 주어진다. 

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

처음 문제를 읽고 음? 뭐지 그냥 탐색 돌려서 연결되어 있는지 없는지만 판별하면 되는거 아닌가? 라고 생각했는데.....

 

정점들의 개수가 최대 1천개이다.

 

각 정점별로 탐색을 한다고 한다면 아마 2초는 아득히 초과할 것이다.

 

그럼 어떤 방법을 써야될까?

 

사실상 여행계획에 있는 도시들이 서로 같은 집합에 속해있는지 없는지만 판별하기 때문에 Union-Find 알고리즘을 이용하면 쉽게 풀 수 있다.

 

그럼 Union-Find 알고리즘이란 무엇이냐?

 

그전에 분리 집합이란 개념부터 알아보자. 분리집합은 간단히 말해 서로소 집합이라고도 부른다. 그럼 서로소 집합이 뭔데?

 

"집합론에서 서로소 집합(-素集合, 영어: disjoint sets)는 공통 원소가 없는 두 집합이다.[1] 예를 들어서 {1, 2, 3}과 {4, 5, 6}은 서로소이며 {1, 2, 3}과 {3, 4, 5}는 아니다."

 

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9

 

라고 위키백과에서 친절하게 설명되어 있다.

 

간단히 말하면 두 집합의 교집합이 공집합인 집합을 의미한다. 아주 쉽게 말하면 겹치는게 없다는 뜻이다.

 

다시 돌아가서 Union-Find 알고리즘은 서로소 집합을 만들어주는 알고리즘이다.

그럼 Union-Find 알고리즘이 어떤식으로 동작하는지 한번 살펴보도록 하자.

 

 

먼저 1부터 7까지 정점이 있다고 가정하자

아래 배열이 의미하는 것은 각 번호들의 부모 번호를 갖고 있고, 초기 상태는 자기 자신의 번호를 갖고 있다.

 

여기서 만약 2번과 3번이 같은 집합이라고 하면, 아래 그림과 같이 합쳐진다고 생각하면 된다.

 

3번 값을 2로 바꿔주면 2번과 3번은 같은 집합에 있다는 뜻이된다.

 

 

만약 5,6,7을 합친다면 어떻게 될까.

위 그림과 같이 합칠 수도 있다. 하지만 밑에다가 계속 달아주는 형태로 집합을 구성하면, 나중에 같은 집합이라는 것을 판별할때 루트 노드로 비교하는데 위와 같이 구성하면 맨 마지막에 있는 노드의 루트가 뭔지를 확인하려면 굉장히 많은 시간이 소요 될 것이다. 따라서 연결 할때 루트를 찾아서 루트 밑에다가 바로 달아 버리는 방법을 이용한다.

 

이렇게 구성할 수 있고, 만약 {2,3} 그룹과 {5,6,7} 그룹이 합쳐진다면 아래 그림과 같이 될 것이다.

그림 레전드

위 방법을 코드로 구현하면 아래와 같다.

//루트 찾기
int find(int num)
{
	if (parent[num] == num)
		return num;
	else return parent[num] = find(parent[num]);
}
//병합
void merge(int num1, int num2)
{
	num1 = find(num1);
	num2 = find(num2);
	if (num1 == num2) return;
	
	parent[num2] = num1;
}

 

이제 문제에 이 방식을 적용시키면, 입력으로 주어진 연결 정보를 이용하여 연결되어 있는 노드들 끼리는 같은 집합으로 만들어주고, 여행계획에 속한 노드들은 i번째와 i+1번째 도시들의 루트번호를 확인후 같으면 같은 집합에 속해 있으니 여행이 가능하다는 뜻이고, 다르면 불가능하다는 뜻이니 NO를 출력해주면 된다.

 

[소스 코드]

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N, M;
vector<vector<bool>> mp;
vector<int> parent;
vector<int> travel;

//루트 찾기
int find(int num)
{
	if (parent[num] == num)
		return num;
	else return parent[num] = find(parent[num]);
}
//병합
void merge(int num1, int num2)
{
	num1 = find(num1);
	num2 = find(num2);
	if (num1 == num2) return;
	
	parent[num2] = num1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	mp.resize(N + 1);
	parent.resize(N + 1);
	travel.resize(M);
	for (int i = 0; i < N + 1; i++) mp[i].resize(N + 1); 

	int tmp;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> tmp;
			if (tmp == 1) mp[i][j] = true;
			else mp[i][j] = false;
		}
	}
	for (int i = 1; i <= N; i++) parent[i] = i;
	for (int i = 0; i < M; i++) cin >> travel[i];


	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (mp[i][j]) merge(i, j);
		}
	}

	
	for (int i = 0; i < M-1; i++)
	{
		if (find(travel[i]) != find(travel[i+1]))
		{
			cout << "NO";
			return 0;
		}
	}
	cout << "YES";
}

 

굳