Hyun's_Devlog

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

유니온 파인드로 접근했다.

풀이

원수를 담는 배열 enemy 2차원 배열을 생성하여 원수 관계가 들어오면 양방향으로 추가.

친구 관계가 입력되면 유니온을 통해 컴포넌트를 합친다.

모든 입력이 들어오고 나면 enemy 배열을 탐색하면서 원수의 원수를 찾아 서로 연결해 주면 된다.

남아있는 컴포넌트의 개수를 출력하면 정답이다.

정답 코드

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

유니온 파인드 문제다. 문제의 내용만 잘 이해한다면 쉽게 풀 수 있는 문제다.

풀이

문제에서 요구하는 것은 모든 뉴럴들을 사이클이 없는 하나의 그래프로 만들려면 몇 번의 연산이 필요한지 구하는 것이다. 역으로 생각하면 주어진 뉴럴들의 연결 상태에서 사이클이 몇 번 일어나는지, 그리고 컴포넌트의 개수를 합산하여 출력하면 된다. 

사이클이 일어난다는 것은 주어진 두 뉴럴의 루트가 같다는 것. 즉 유니온이 일어날 때, 두 노드의 루트를 확인하는데, 이때 루트가 같다면 연결을 끊어내는 작업을 해야 하므로 연산 횟수 1 증가.

최종 컴포넌트의 상태를 확인할 때, 컴포넌트가 2개 이상이라면 하나로 합치는 연산을 수행하므로 (총 컴포넌트 개수 - 1) 횟수를 추가하여 출력하면 된다.

정답 코드

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

기하학이 한 방울 들어간 유니온 파인드 문제. 이전에 풀다가 포기했던 문제다. 거리 계산 부분에서 아무 생각 없이 2차원 배열로서의 거리로 접근했는데, 옳은 방법이 아니었다. 2차원 배열 없이 풀 수 있는 문제.

풀이

입력되는 좌표와 범위를 입력받을 때마다, 모아놓은 나머지 지점들과의 거리를 계산, 범위가 겹치는 경우 유니온을 수행하여 마지막에 그룹의 개수를 출력하면 된다.
이번에는 그룹의 노드 개수를 파악하는 문제는 아니므로, 합병 수행 시 루트의 값은 바꾸지 않고 자식으로 들어갈 노드의 번호만 루트의 번호로 바꾸어 주면 된다.
두 지점의 범위 판정은 간단하다. 두 원점 사이의 거리가 두 지점의 범위의 총합보다 같거나 짧은 경우, 범위가 겹치는 것으로 판단하면 된다.

정답 코드

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

유니온 파인드 문제다. 바로 이전 풀이 [11816] 로봇 조립 문제와 같은 방법으로 접근하면 풀 수 있다.

풀이

지난번 문제와의 차이점은 은하에 속한 행성의 개수가 처음부터 주어진다는 점이다. 배열 galaxy의 초기값을 0으로 설정하고 행성의 개수가 입력될 때 해당 값만큼 빼주고 시작하면 된다.

은하가 연결될 때마다 연결된 은하의 행성 수를 출력해야 하므로 유니온 함수에 결합 동작 이후 배열의 루트에 해당하는 값을 절댓값으로 출력하면 된다.

정답 코드

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

기본적인 유니온 파인드 문제다. 대신 문제에서 요구하는 것은 부품이 속한 컴포넌트의 크기이다. 

풀이

부품의 번호가 1부터 1,000,000이기에 입력 인덱스를 바로 핸들링 하기 위해 1,000,001 개의 배열을 생성. 초기값을 -1로 둔다. 여기서 -1은 루트라는 것을 표시함과 동시에 컴포넌트의 개수를 음수로 표현하는 역할도 하게 된다.

파인드에 해당하는 root() 함수를 통해 배열의 값을 탐색, 값이 0보다 작으면 루트인 것으로 판정, 0보다 큰 값이면 해당 부품의 부모인 것으로 판정하고 부모의 루트를 재귀 호출하여 컴포넌트의 루트를 탐색한다.

유니온에 해당하는 union() 함수는 둘의 루트를 확인 후, 서로 다른 컴포넌트라면 합치는 과정을 수행하는데, 루트가 될 노드에 추가될 노드의 값을 더해주는 것으로 컴포넌트의 크기를 갱신하게 되고, 다른 컴포넌트로 편입하게 될 루트에는 해당 루트의 번호를 대입해주는 것으로 편입을 마치면 된다. 

마지막으로 출력해야 할 경우에는 해당 부품의 루트를 찾고, 루트를 인덱스로 배열의 음수 값을 절댓값으로 출력해주면 된다.

정답 코드