c언어 1976번 여행 가자 (백준)

#include <stdio.h>
#include <stdlib.h>

int find(int parent[], int x) {
	if(parent[x] == x) return x;
	return parent[x] = find(parent, parent[x]); 
}

void merge(int parent[], int x, int y) {
	x = find(parent, x);
	y = find(parent, y);
	if(x != y) parent[x] = y;
	return;
}

int same(int parent[], int x, int y) {
	x = find(parent, x);
	y = find(parent, y);
	return x == y;
}

int main(void) {
	int n, m;
	scanf("%d", &n);
	scanf("%d", &m);
	int* parent = (int*) malloc(sizeof(int) * (n+1));
	for(int i=1; i<=n; i++) parent[i] = i;
	
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			int tmp = 0;
			scanf("%d", &tmp);
			if(tmp) merge(parent, i, j);
		}
	}
	
	int before = 0;
	int i=0;
	for(i=0; i<m; i++) {
		int tmp = 0;
		scanf("%d", &tmp);
		if(before) {
			if(!same(parent, before, tmp)) {
				break;
			}
		}
		before = tmp;
	}
	
	if(i==m) printf("YES");
	else printf("NO");	
	
	
}

 

풀이 : union(합집합) find(찾기)

 

1. n, m을 입력받습니다.

2. 모든 도시의 연결 정보를 입력 받고, 연결이 되있다고 한다면, 같은 집합으로 (merge) 묶습니다.

3. m만큼의 여행 계획을 입력 받으며, 받는 동안, 전에 도시와 지금 입력받은 도시가 연결되어 있는지를 확인합니다.

만약 반복문 도중에 연결이 되지 않았다면, break을 한 다음, NO을 출력하며, 반복문을 다 돌고 나오면 모든 여행계획에 있는 도시들이 연결되어있다는 의미이므로 YES를 출력합니다.

 

 

 

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

1976번: 여행 가자