Hyun's_Devlog

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

누적합과 이분 탐색을 통해 접근하였다.

풀이

두 배열의 누적합을 통해 부 배열을 생성, 두 개의 부 배열 중 하나의 부 배열을 오름차순 정렬한 뒤 이분 탐색을 수행, (T - 다른 부배열의 원소) 값을 찾아낸다면 해당 값의 개수만큼 정답을 추가하여 마지막에 출력하면 된다.

정답 코드

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

유니온 파인드와 플로이드 와샬로 접근 가능한 문제다. 문제 속 함정에 걸려 시간을 많이 소비한 문제다. 문제를 꼼꼼히 읽도록 하자.

풀이

입력받은 간선 정보를 통해 유니온 파인드를 통해 컴포넌트를 구분, 2차원 배열을 통해 각 노드 간의 거리를 갱신한다. 입력이 완료되면 플로이드 와샬 알고리즘을 통해 각 노드 간의 최소거리를 구한다. 

유니온 파인드를 통해 알게 된 루트 노드를 입력하면 해당 컴포넌트의 최소 의사전달시간을 구하면 된다. 여기서 주의할 점은 문제에 주어진 "위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록"이라는 부분이다. 해당 부분이 무엇인지 잘 생각하고 접근해야 한다.

다음으로 주의할 점은 "각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다." 부분이다. 처음에 아무 생각 없이 0부터 n까지 순번으로 탐색하면 당연하게 순번대로 출력이 될 거라고 생각했으나, 낮은 순번의 루트를 호출하여 더 높은 번호가 대표가 되는 경우가 존재한다. 결국 대표의 번호를 따로 담아 정렬한 뒤에 출력해주었다.

정답 코드

조건에 대한 이해력이 너무나도 중요한 문제였다.

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

유니온 파인드 문제다. 문제는 같지만 입력 범위가 넓은 14595 문제를 풀다가 시간 초과하여 범위가 좁은 해당 문제부터 풀어보았다.

풀이

들어온 입력에 맞게 범위 단위로 유니온을 해준뒤 루트의 개수를 세면 된다. x < y 라는 조건이 있으니, x의 루트만 찾아낸 후 x+1 ~ y 범위까지 전부 x의 루트로 변경하면 된다.

정답 코드

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/10216

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

풀이

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

정답 코드