인프런 커뮤니티 질문&답변

starkshn님의 프로필 이미지

작성한 질문수

Do it! 알고리즘 코딩테스트 with C++

유니온 파인드 (Union-Find)

백준 1876여행 유니온 파인드 질문있습니다.

24.01.02 12:38 작성

·

177

0

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define ll long long
#define endl "\n"

void merge(int a, int b);
int find(int a);
vector<int> parent;
vector<int> paths;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n; 
	cin >> m;

	parent.resize(n + 1);

	for (int i = 0; i <= n; ++i)
	{
		parent[i] = i;
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			int v;
			cin >> v;
			if (v == 1)
			{
				merge(i, j);
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		int n;
		cin >> n;
		paths.push_back(n);
	}

	int prevPath = find(paths[0]);
	for (int path : paths)
	{
		int curPath = find(path);

		if (curPath != prevPath)
		{
			cout << "NO";
			return 0;
		}

		prevPath = curPath;
	}

	cout << "YES";

	return 0;
}

void merge(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a != b)
		parent[b] = a;
}

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

	return parent[a] = find(parent[a]);
}

왜맞틀인거같은 느낌이 듭니다.
책에 있는 내용 분석해서 이해는 하였는데 제가 짠 코드가 왜 틀린것인지 모르겠습니다.

의심되는 부분은 처음에 merge하는 for문인거같은데
책처럼 인접리스트를 사용하지 않고 v가 1이라면(i행과 j열이 연결되어 있다면) 그냥 바로 merge하여 병합하였는데 이부분에 예외가 있는것인지 아니면 다른 부분에서 예외가 있는것인지 감이 안 잡히는데 어디가 잘 못된것인지 한번 봐주실 수 있나요?

감사합니다 :)

답변 1

0

하루코딩님의 프로필 이미지
하루코딩
지식공유자

2024. 01. 03. 00:37

안녕하세요. 반갑습니다.

아마도 Path를 저장하는 반복문에 약간 로직이 잘못된 것으로 보입니다.

 

해당 부분을

for (int i = 1; i <= n; ++i) {
   int n; 
   cin >> n; 
   paths.push_back(n); 
}


아래와 같이 수정하시면 되지 않을까 싶습니다.

for (int i = 1; i <= m; i++)
{
    int path;
    cin >> path;
    paths.push_back(path);
}	

 

감사합니다.

새해 복 많이 받으세요 :)

 

starkshn님의 프로필 이미지

작성한 질문수

질문하기