Beakjoon] 여행 가자(백준 1976코테) - 그래프 (C++)

---

🅰️문제주소 : https://www.acmicpc.net/problem/1976

 

🚩문제 

 

 

🪡풀이 

 - 이동하기 원하는 길이 모두 이어져있는지 union find를 통해 간단하게 찾을 수 있다
 - 각 노드(도시)가 이어진 루트 노드를 별도의 배열에 저장해 둔다.
 - 이어진 길은 union find로 재귀 탐색하며 루트노드의 값으로 업데이트시킨다
 - 트리구조에서 스타구조 모형으로 점점 변해가며 시간복잡도가 줄어든다.

 

 

☕코드는 아래 숨김

#include <iostream>
#include <vector>


std::vector<int> ROAD;


int find(int a) {
	if (a == ROAD[a])
		return a;
	return ROAD[a] = find(ROAD[a]);
}

void UnionFunc(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		ROAD[b] = a;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int city_num, wish_num;

	std::cin >> city_num;
	std::cin >> wish_num;
	std::vector<std::vector<int>> MAP;
	int WISH[1001];

	MAP.resize(city_num+1, std::vector<int>(city_num+1, 0));
	ROAD.resize(city_num + 1);	

	for (int i = 1; i <= city_num; ++i) {
		for (int j = 1; j <= city_num; ++j) {
			std::cin >> MAP[i][j];
		}		
		ROAD[i] = i;
	}

	for (int i = 1; i <= wish_num; ++i) {
		std::cin >> WISH[i];
	}

	for (int i = 1; i <= city_num; ++i) {
		for (int j = 1; j <= city_num; ++j) {
			if (MAP[i][j] == 1) {
				UnionFunc(i, j);
			}
		}
	}

	int index = find(WISH[1]);
	bool connect = true;

	for (int i = 2; i <= wish_num; ++i) {
		if (index != find(WISH[i])) {
			std::cout << "NO" << "\n";
			connect = false;
			break;
		}
	}

	if (connect)
		std::cout << "YES" << "\n";
	
	return 0;
}

 

💡알게 된 것 

 - 오래간만에 푼 코테문제라 union find를 remind 함
 - union find는 쉬운 개념에다가 구현도 엄청 간단하기에 반드시 알고 있다가 적절할 때 적용해야 한다
 - 메모리 부족이 처음에 떴는데 vector를 줄이고 array변경하니 해결되었다

---