백준 9172 _ 상근이의 여행

2020-04-04 · 배운 것 · 3분 읽기

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

9372번: 상근이의 여행

1. 풀이방법

문제를 보자마자 정점-1을 출력하면 되지않나? 라는 의문이 들었고 정답처리가 되긴했다.
하지만, 정점 -1 출력은 너무 허무해서 나는 한번 아까 한번본 유니온 파인드의 개념을 이용해서 풀어보기도 했다.

union -find -> 최상위 부모노드를 저장하는 배열을 만들고 정점을 이을때마다 배열의 값을 갱신한다.

2. 코드 ( 첫번째 풀이 (정점 -1)만 출력하면 답임, 두번째 풀이만 올리겠음 )

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> edge;
int parents[1002];
int N;
void parentsInit(int n)
{
	for (int i = 1; i <= n; i++)
		parents[i] = i;
}

int getParent(int n)
{
	if (parents[n] == n) return n;
	return parents[n] = getParent(parents[n]);
}

void update(int ori, int change)
{
	for (int i = 1; i <= N; i++)
		if (parents[i] == ori)
			parents[i] = change;
}

void makeUnion(int a, int b)
{
	int x = getParent(a);
	int y = getParent(b);
	if (x < y)
		update(y, x);
	else
		update(x, y);
}

int main()
{
	int t;
	cin >> t;

	int n, m;
	for (int i = 0; i < t; i++)
	{
		cin >> n >> m;
		N = n;

		parentsInit(n);
		int result = 0;

		//간선 입력
		int a, b;
		for (int j = 0; j < m; j++)
		{
			cin >> a >> b;
			edge.push_back({ a, b });
		}

		//간선을 전체 순회하며 계산
		for (int j = 0; j < (int)edge.size(); j++)
		{
			int firstPlace = edge[j].first;
			int secondPlace = edge[j].second;
			if (parents[firstPlace] != parents[secondPlace])
			{
				makeUnion(firstPlace, secondPlace);
				result++;
			}
		}

		cout << result << '\n';
		edge.clear();
	}

	return 0;
}

3. 후기

유니온 파인드의 개념과 설명을 유명한 블로그에서 보고 이용해서 짜봤는데 처음짜는거라 그런지 솔직히 더럽게 못짰다. 또 뭔가 유니온 파인드를 잘못짠거 같기도 한데 ..

아.. 틀린거 같아서 다시 공부해보니 위에것은 유니온 파인드 알고리즘도 뭣도 아닙니다. 잘못짰네요.