[백준 1976] 여행 가자 (자바)

 

난이도 : 골드 4

 

도시들을 연결하여 주어진 도시가 하나로 이어져 있는지 확인하는 문제입니다.

이러한 문제는 유니온 파인드(Union-Find)를 이용하여 풀 수 있습니다.

유니온은 도시들을 묶고 파인드는 이러한 도시의 대표를 찾습니다.

그룹의 대표를 그 그룹에서 가장 작은 값으로 정했습니다. 대표는 그룹마다 통일성을 가진다면 어떤 값으로 해도 상관은 없습니다. 단, 이 대표를 통하여 그룹을 구분할 수 있어야 합니다.

 

예를 들면 [1, 2, 3, 4, 7, 8], [5, 6], [9]의 그룹은 각 그룹의 대표를 1, 5, 9로 설정합니다.

각 그룹의 대표를 저장하는 parent배열을 위와 같이 나타내 볼 수 있습니다.

최적화를 위해 그룹의 대표를 건드릴 때는 find를 이용합니다. parent 절대 xxxx.

parent를 이용하면 초기에 연결되고 최적화되지 않았을 경우가 있으므로 오답 발생 가능성이 있습니다.

union과 find 함수를 통해 최적화를 하는데 연결되고 호출되지 않았다면 초기값을 계속 가지고 있으므로 find함수를 통하여 최적화 + 올바른 대푯값을 불러옵니다.

2020/11/06 - [정보/CS] - Union-Find 유니온 파인드

Union-Find 유니온 파인드

여기서 관련 내용을 읽을 수 있습니다.

---

전역 변수

int n = 도시의 수

int parent[] = 그룹의 대표를 나타내는 배열

 

함수

void main

입력을 받고 2차원 배열을 읽어서 도시를 연결해줍니다.

여행할 도시를 입력받고 각 도시의 대표를 비교하여 모두 같으면 "YES" 그렇지 않으면 "NO"를 출력합니다.

(union 호출)

 

void union

두 개의 파라미터를 서로 연결합니다. 각 도시의 그룹 대표를 p1, p2로 구합니다.

그리고 그룹의 가장 작은 값이 그룹 대표가 되므로 작은 값을 기준으로 넣어줍니다.

이때 주의할 점은 대푯값을 기준으로 작업을 합니다. 즉, 42~45번째 줄에서 parent[p1] = p2처럼 대표 값을 조작합니다.

 

int find

입력 받은 수의 대푯값을 반환합니다.

재귀를 통해 구현했으며 재귀 과정에서 최적화를 거칩니다. 종료 시점은 파라미터의 대표가 곧 자신일 때(그룹의 가장 작은 수)입니다.