Hyun's_Devlog

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

유니온파인드와 그래프탐색으로 접근했다.

풀이

모든 정점을 방문하게 된다면 시간초과가 일어난다.

예제를 보면 3~1, 3~5, 3~4, 3~2, 6~4, 6~2 총 6개의 구간이 정답이다.

검은색 정점을 시작으로 빨간색 정점으로만 이어지는 경로의 개수. 즉 우리는 연속되는 빨간색 정점을 컴포넌트로 묶어 개수를 미리 저장해 놓으면 보다 빠르게 탐색이 가능해진다.

따라서 인접한 빨간색 정점끼리는 유니온을 통해 하나의 컴포넌트로 묶어내어 개수를 저장하고, 컴포넌트에 인접한 검은색 정점의 개수를 파악하면 해당 컴포넌트에서 발생되는 누텔라 트리의 개수를 구할 수 있게 된다. 

해당 과정은 bfs를 통해 O(N)만에 정답을 구할 수 있다.

정답 코드

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

그래프 탐색과 유니온파인드로 접근했다.

풀이

정점 N개와 간선 N개를 가진 트리는 한 개의 사이클을 가지고 있는 트리이다. 따라서 정점 u에서 v로 가는 경로가 사이클을 거쳐가게 된다면 경로는 2개가 되고, 경로에 사이클이 없다면 경로는 1개가 되는 것이다.

따라서 사이클에 속해있는 정점을 파악한 뒤 유니온 파인드를 수행하다. 연결하려 하는 두 정점의 경로가 사이클에 속한 경로라면, 정점을 연결하지 않고 넘어간 뒤, 쿼리가 주어질 때, 두 정점의 부모가 같다면 1 아니면 2를 출력하면 정답이다.

주어진 예제를 통해 보면 정점 1 - 2 - 3으로 사이클이 이루어진다. 따라서 정점 1, 2, 3 사이의 간선을 없애고 쿼리에서 서로 다른 컴포넌트의 경로를 물어보면 해당 경로는 사이클을 통한 경로가 있다는 뜻이므로 2를 출력, 같은 컴포넌트 내의 경로를 물어보면 1을 출력하면 된다.

사이클 검출은 진입차수가 1인 정점부터 너비 우선 탐색을 수행하여 찾아내었다. 

정답 코드

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

유니오 파인드와 그래프 탐색으로 접근했다.

풀이

2차원 지도를 1차원 배열로 매핑한 뒤 지도에 적힌 움직임 대로 그래프 탐색을 수행한다.

탐색을 수행하면서 현재 위치와 다음으로 이동할 위치의 번호끼리 합병해 주면 된다.

컴포넌트의 개수를 출력해 주면 정답이다.

단, 중복 방문을 막는 과정에서 실수하여 WA를 받았다.

반례는 문제에 주어진 예제를 보고 생각해 냈다.

3 4

SWWW

SEEN

EEEN

방문했던 위치여도 아직 방문하지 않은 곳에서 진입이 가능하기에 방문했던 위치도 무조건 유니온 동작을 수행해야 한다.

정답 코드

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

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

풀이

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

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

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

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

정답 코드

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

유니온 파인드 문제다. 푸는데 시간이 좀 걸렸다.

풀이

루트여부 및 원소의 크기정보, 배수로 용량, 강수량 정보를 담은 원소 n개의 배열을 생성하여 유니온 파인드를 수행한다. 여기서 중요한 점은 쿼리입력을 받을 때, 중간마다 출력을 요구한다는 점이다.

처음에는 출력을 요구하는 2가 입력될 때마다 배열을 전부 탐색하여 루트노드를 만나면, 홍수여부를 체크한 뒤 원소의 개수만큼 개수를 계산하여 출력하였으나, 시간초과를 받았다.

보통 시간복잡도를 계산할 때 1초당 1억 연산으로 따진다. 쿼리가 전부 2라면, 배열의 최댓값*쿼리 최댓값(100000*100000)으로 시간초과는 당연한 결과였다. 

따라서 생각해낸 풀이는 처음 정보가 주어지고 나면 배열을 탐색해 홍수가 나는 지역의 개수를 전역변수로 파악. 이후 유니온이 일어날 때마다 해당 지역이 홍수가 일어나는지, 일어나지 않는지를 파악해 전역변수를 갱신하는 것으로 접근하였더니 시간초과를 피할 수 있었다.

정답 코드

언제쯤이면 고수가 될 수 있을까..

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

[2610] 회의준비와 결이 비슷한 문제다. 

풀이

유니온파인드와 그래프탐색으로 접근했다. 가중치가 큰 순으로 간선을 정렬한 뒤 순서대로 유니온을 수행, 루트가 같다면 결합하지 않는다.

이후 입력되는 출발지와 도착지를 기준으로 너비우선탐색을 수행. 그래프를 탐색하면서 가중치를 수정해나가면 된다. 

처음에는 (k횟수만큼) 그래프와 루트정보를 매번 초기화하고, 입력되는 출발지와 도착지를 기준으로 유니온을 하면서 그래프를 탐색했으나, 시간초과발생. 생각해보니 간선을 한 번만 탐색하고도 cost를 출력할 수 있게 접근이 가능했었다.

정답 코드

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

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

풀이

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

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

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

정답 코드

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

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

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

풀이

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

정답 코드