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

문제

[C++] 백준 1976: 여행 가자 GOLD 4
https://www.acmicpc.net/problem/1976

 

---

 

접근 방법

백준 1976번은 여행 계획이 가능한지 판단하는 문제다.

여러 도시가 있고, 도시 간 연결 정보가 주어질 때 주어진 여행 계획대로 모든 도시를 이동할 수 있는지 확인해야 한다.

 

핵심 아이디어는 다음과 같다.

여행 계획에 포함된 모든 도시가
하나의 연결된 그룹(같은 집합) 에 속해 있는지 확인하면 된다.

 

이 문제는 도시 간 연결 여부를 계속 확인해야 하므로
Union-Find(Disjoint Set) 자료구조를 사용하는 것이 가장 효율적이다.

 

상세 아이디어

부모 배열 초기화

parent.resize(N + 1, 0);
for (int i = 1; i <= N; i++)
    parent[i] = i;

각 도시는 처음에 자기 자신을 부모로 가지는 독립적인 집합이다.

 

연결 정보로 집합 구성

도시 간 연결 여부는 인접 행렬 형태로 주어진다.

for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= N; j++)
    {
        cin >> num;

        if (num == 1)
            unionfunc(i, j);
    }
}

 

• num == 1이면 i와 j가 연결된 것이므로 같은 집합으로 합친다.
• 이렇게 하면 연결된 도시들은 하나의 그룹으로 묶인다.

 

여행 계획 검증

cin >> num;
int P = find(num);​

첫 번째 도시의 대표 노드를 기준으로 잡는다.

 

이후 나머지 도시들에 대해 대표 노드가 다르면 → 같은 집합이 아님 → 이동 불가능

if (find(num) != P)
{
    ret = false;
    break;
}​

 

모든 도시가 같은 대표 노드를 가지면
여행 계획은 가능하다.

 

구현 시 주의할 점

• Union-Find를 사용해야 시간 초과를 피할 수 있다.
  단순 DFS/BFS를 매번 돌리면 비효율적이다.
• 연결 정보는 인접 행렬 형태로 주어지므로 이중 반복문으로 입력을 처리해야 한다.
• union 연산은 반드시 대표 노드끼리 연결해야 한다.
• 여행 계획의 첫 번째 도시를 기준으로 모든 도시의 대표 노드가 같은지 비교해야 한다.
• 하나라도 다르면 즉시 종료해도 된다. (불필요한 탐색 방지)

 

 

---

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent;

int find(int x)
{
	if (parent[x] == x)
		return x;
	else
		return parent[x] = find(parent[x]);
}
void unionfunc(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a != b)
		parent[b] = a;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N = 0, M = 0;
	cin >> N >> M;

	parent.resize(N + 1, 0);
	for (int i = 1; i <= N; i++)
		parent[i] = i;

	int num = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> num;

			if (num == 1)
				unionfunc(i, j);
		}
	}
	
	cin >> num;
	int P = find(num);
	bool ret = true;
	for (int i = 1; i < M; i++)
	{
		cin >> num;

		if (find(num) != P)
		{
			ret = false;
			break;
		}
	}
	if (ret)
		cout << "YES";
	else
		cout << "NO";
}