본문 바로가기
백준

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

by MY블로그 2023. 5. 30.
 

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

지난번에이어 이번에도 Union-Find 알고리즘을 이용해야하는 문제 입니다.

아직 Union-Find 알고리즘에 익숙하지않기때문에 참고 합니다.

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

// 백준 1976번 여행 가자 ( Union - Find 문제 )

int n, m; // 도시의수 n, 여행계획에 속한 도시들의수 m
int p[200]; // 도시의 수는 최대 200

int find(int x) { // 탐색
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

void union_node(int x, int y) { // 노드 합치기
	x = find(x);
	y = find(y);
	if (x < y) p[y] = x;
	else p[x] = y;
}

int main(void) {
	fastio;
	cin >> n >> m; // 도시의수 n, 여행계획에 속한 도시들의수 m

	for (int i = 1; i <= n; i++) p[i] = i;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int x;
			cin >> x;
			if (x == 1) {
				union_node(i, j);
			}
		}
	}
	int root;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		if (i == 0) root = find(x);
		else {
			if (find(root) != find(x)) { // 루트노드가 일치하지않으면 (경로 없음)
				cout << "NO";
				return 0;
			}
		}
	}
	cout << "YES"; // 루트노드가 일치하는경우에만 출력
	return 0;
}

2가지 풀이 방식을 참고할 수 있는 블로그 입니다.

 

백준 1976 C++ 여행 가자

나만 빼고 다 Union Find 로 풀고있었다

velog.io

 

'백준' 카테고리의 다른 글

[백준/C++] 11286 절댓값 힙  (0) 2023.08.07
[백준/C++] 1874 스택수열  (0) 2023.06.13
[백준/C++] 1717 집합의 표현  (0) 2023.05.24
[백준/C++] 14888 연산자 끼워넣기  (1) 2023.05.21
[백준/C++] 1912 연속합  (0) 2023.05.18

댓글