Hyun's_Devlog

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

유니온 파인드 문제다. 오일러 경로를 이용해야 한다.

풀이

문제에서 주어지는 것은 모든 간선을 한 번에 이용하면서 모든 노드의 순회가 가능하냐는 것이다. 즉 주어진 도형을 한 손 그리기가 가능하냐로 생각이 가능하다. 

이에 관한 공식이 있는지 찾아보았는데, '오일러 경로'에 대한 자료를 찾을 수 있었다. 각 노드의 진입, 진출 차수의 합이 짝수이면 한붓그리기가 가능하며, 예외적으로 차수가 홀수인 것이 2개라면 한붓 그리기가 가능하다고 한다.

차수가 홀수인 것이 0개 또는 2개라면 한붓그리기가 가능하다

따라서 문제에서 요구하는 것을 요약하자면, 모든 정점이 하나의 컴포넌트인지, 그렇다면 각 노드의 차수가 홀수인 경우가 0 또는 2라면 해당 그래프는 퍼레이드가 가능한 그래프인 것으로 출력하면 된다.

정답 코드

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

최소 스패닝 트리 문제다. 단 여기서 간선의 비용이 최대가 되게 구하면 된다. 주의할 점은 숭이가 위치한 곳과 혜빈이가 위치한 곳이 다리로 연결된다는 보장이 없다는 것을 숙지하고 풀어야 한다. 이것 때문에 오답 판정을 받았다.

풀이

입력되는 간선의 가중치, 즉 무게가 높은 순으로 간선의 정보를 정렬한 뒤, 가중치가 높은 순서로 유니온을 수행한다. 유니온을 수행할 때마다 들고 갈 수 있는 빼빼로의 무게를 작은 값으로 갱신, 마지막으로 숭이와 혜빈이의 위치가 같은 컴포넌트에 속해있는지 확인한 후, 같은 컴포넌트가 아니라면, 빼빼로를 전달할 수 없는 것이므로 0을 출력, 같은 컴포넌트가 맞다면 갱신해온 무게 값을 출력하면 된다.

정답 코드

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

유니온 파인드 문제다. 추가적으로 그래프 탐색을 통해 접근했다.

풀이

문제에 "지도 밖으로 나가는 방향은 주어지지 않는다"는 입력 조건이 있다. 그 얘기는 주어지는 좌표 어느 부분이던 탐색 시 무조건 사이클이 일어난다는 것이고, 문제의 답은 사이클이 일어나는 영역에 하나씩 "safe zone"을 설치하면 된다는 이야기. 요약하자면 깊이 우선 탐색을 통해 유니온파인드를 통해 컴포넌트의 개수를 반환하면 되는 것이다.

예제의 입력을 기준으로 사이클이 일어나는 영역을 색으로 표시해 놓았다. 두 개의 구역으로 나뉘며, 구역 하나당 하나의 "safe zone"을 설치하면 최소 개수를 구할 수 있다.

고민했던 점은 유니온을 할 때, 어떻게 구별하느냐인데, 이전에 풀었던 문제에서 2차원 배열을 번호로 매겨서 1차원 배열에 대입하여 풀었던 기억이 나서 그 부분을 사용했다. 즉 깊이 우선 탐색을 하면서 해당 위치의 번호와 다음 위치의 번호를 유니온, 루트가 같다면 종료. 모든 좌표에 대해서 깊이 우선 탐색을 수행한 뒤, 컴포넌트의 개수를 출력해주면 된다.

정답 코드

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

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

풀이

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

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

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

정답 코드

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

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

정답 코드