백준1976 - 여행 가자

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

1976번: 여행 가자

공통 조상 찾기 문제를 풀고 싶어서 도전한 문제이다.. 조상을 합치는 부분과 조상을 찾는 부분과 조상이 같은지 확인하는 부분으로 이루어진다.

 

문제에서는 주어진 경로대로 모든 도시를 탐색할 수 있는지 묻고 있다. 서로 다른 도시들의 조상이 같다면 어떤 방법을 써도 이동이 가능하다. 그래서 공통 조상 찾기 알고리즘으로 풀었다.

 

조상이 같은지 찾는 부분을 여기서는 사용하지 않고 배열을 이용하여 조상이 같은지 체크하였다.

 

N * N으로 각 도시가 연결이 되었는지 표현한다. 여기서 (i, j)의 결과가 1이면 두 도시가 연결되었다는 것으로 unionParent함수를 이용하여 두 도시의 조상을 합친다.

 

두 도시의 조상이 같은지 판별하는 방법은 벡터에 여행하기 원하는 도시들을 넣어 두 개씩 조상이 같은지 확인하는 방법으로 검출하였다.

 

#include <iostream>
#include <vector>
#define MAX 201
using namespace std;

int set[MAX]; //도시의 최고 부모
int mat[MAX][MAX]; //도시의 연결 정보
int N, M; //N개의 마을, M개의 여행할 도시의 갯수
int num; //여행할 도시
bool check = true; //여행이 가능하지 체크하는 변수
vector<int> v; //여행할 도시들을 저장하는 공간

//처음에 모든 도시의 최고 부모는 자기 자신이다.
void setting() {
	for (int i = 0; i < MAX; i++) {
		set[i] = i;
	}
}

//최고 부모를 얻는 함수
int getParent(int set[], int x) {
	if (set[x] == x) return x;
	else return set[x] = getParent(set, set[x]);
}

//최고 부모가 같은지 찾는 함수
bool findParent(int set[], int x, int y) {
	x = getParent(set, x);
	y = getParent(set, y);

	if (x == y) return true;
	else return false;
}

//최고 부모를 합치는 함수, 최고 부모가 작은 쪽으로 합친다.
void unionParent(int set[], int x, int y) {
	x = getParent(set, x);
	y = getParent(set, y);

	if (x < y) set[y] = x;
	else set[x] = y;
}

int main() {
	setting();

	cin >> N;
	cin >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> mat[i][j];
			if (mat[i][j]) unionParent(set, i, j); //(i, j)의 결과가 1이면 두 도시는 연결이 되었다.
		}
	}
	for (int i = 0; i < M; i++) {
		cin >> num;
		v.push_back(num);
	}
	for (int i = 0; i < v.size() - 1; i++) {
		if (set[v[i]] != set[v[i + 1]]) { //서로 다른 두 도시의 조상이 다르다면
			check = false; //여행할 수 없다.
			break;
		}
	}

	//여행할 수 있는 여부에 따라서 YES와 NO를 출력한다.
	if (check) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}
}