Hyun's_Devlog

유니온 파인드로 접근하였다.

풀이

문제의 핵심은 가중치가 주어지는 간선은 오로지 한 개라는 것. 즉 가중치가 있는 간선을 거쳐가는 경로의 개수를 찾는 문제다. 가중치가 없는 간선들을 먼저 연결해 준 뒤 마지막으로 가중치가 존재하는 간선을 연결할 때, 연결하려는 두 컴포넌트의 개수를 서로 곱해주면 해당 간선을 거쳐가는 간선의 개수를 구할 수 있게 된다. 예제를 기준으로 그림으로 설명하면 다음과 같다.

2번 정점과 3번 정점을 연결할 때, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5의 경로에서 2-3 간선을 이용해야만 한다. 즉 2번 정점이 속한 컴포넌트의 정점개수와 3번 정점이 속한 컴포넌트의 정점 개수를 서로 곱해주면 정답이다.

단, 예제입력 2와 같이 가중치가 존재하는 간선을 연결할 때 이미 두 정점이 같은 컴포넌트인 경우 비용 0인 간선으로 우회가 가능하기에 이때는 정답이 0이다.

따라서 유니온 파인드 알고리즘을 통해 각 컴포넌트의 개수를 핸들링하여 정답을 출력해 주면 된다.

정답 코드

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

기본적인 MST 문제다. 

풀이

두 가지 방법으로 풀었다. 첫 번째로 접근했던 방법은 시간이 조금 빠르지만 코드가 조금 더 길어진다. 

간선의 가중치가 작은 순서로 두 정점 U, V를 연결할 때, 조건을 추가했다. 

두 정점에 워프를 설치하는 비용 > 두 정점을 연결하는 간선 비용 + min( U정점에 워프 설치 비용, V정점에 워프 설치 비용)

두 정점에 탈출구 워프를 설치하는 비용이 더 저렴하다면 두 정점은 연결하지 않는다. 반대로 두 정점에 탈출구 워프 설치 비용이 더 비싸다면 간선을 연결하고 워프를 설치비용이 더 저렴한 쪽이 루트가 되어 연결하면 된다.

이후 각 컴포넌트의 루트 정점에 워프설치 비용을 더해주면 가장 작은( 간선 + 워프 설치 ) 비용이 나오는데, 마지막으로 한번 더 모든 정점에 워프 설치비용과 비교하여 더 작은 쪽을 출력하였다.

두 번째 방법은 탈출구를 0번 정점으로 취급하여 간선정보를 정렬한 뒤 MST를 수행하면 간단하게 구할 수 있다.

정답 코드-1

정답 코드 - 2

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

MST 알고리즘의 기본문제다. 크루스칼 알고리즘을 통해 해결했다.

유니온 함수의 구현에서 사소한 실수를 해서 WA를 받아 당황했지만 실수를 금방 발견했다.

풀이

주어지는 간선은 양방향 간선이므로 u (0 ..< N), v (u+1 ..< N) 탐색을 통해 중복되는 정보는 배제하고 탐색하였다.

간선이 음수면 이미 연결된 고속도로 이므로 절댓값을 totalCost에 더한 뒤, 두 정점을 연결한다. 주의할 점은 이미 부모가 같은 정점끼리의 간선이 음수로 주어질 수도 있으므로 있으므로 예외처리를 해주어야 한다.

나머지의 경우는 edges 배열에 담아낸 뒤 비용이 적은 간선부터 유니온 함수를 수행한다. 이때 연결된 간선은 배열에 따로 정보를 담아주었다가 출력해 주면 된다.

정답 코드

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

배열에 관련된 구현문제다.

풀이

일반적인 풀이 방법은 문제에 주어진 대로 2차원 배열을 탐색하여 반시계방향으로 요소를 옮겨주면 된다.

각 그룹이 R번 회전해야 하므로 이 방법으로 구현하게 된다면 O(N*M*R)에 해결할 수 있다.

하지만 swift의 경우 다른 언어에 비해 느려서 해당 방법으로는 시간초과를 받는다.

R번 회전한다는 것은 결국 원점으로 돌아올 수 있다는 것이고 이는 곧 회전 수를 줄일 수 있는 요인이라 생각했다. 문제는 회전해야 하는 그룹의 크기가 전부 달라서 이를 어떻게 해결할까 고민하였다.

https://www.acmicpc.net/board/view/86800

질문 탭을 보니 2차원 배열을 1차원으로 접근해 보라는 힌트를 발견. 해당 힌트를 통해 문제를 해결할 수 있었다.

입력예제 1을 기준으로 설명하면 다음과 같다.

회전시켜야 할 그룹을 파악한 후 1차원 배열로 생성.

(R % 각 배열의 크기) 부분에서 분리하여 순서를 바꾼 배열을 만든다.

이어서 다시 회전시켜야 할 그룹의 자리에 1차원 배열의 요소를 담아주면 O(2*N*M)만에 결과를 얻을 수 있다.

정답 코드

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

스택을 활용한 문제다. 

풀이

입력되는 모든 키를 비교하게 되면 당연하게도 시간초과가 일어난다. 풀이를 찾아보니 스택을 사용한다면 O(N) 만에 탐색이 가능했다.

우선 주어지는 현재 키를 순서대로 스택에 담아낼 것이다. 

(키 높이, 인원)를 담는 비열을 생성하여 현재 주어진 키와 스택의 top과 비교하여 쌍을 계산하면 된다. 

스택이 비어있다면 당연하게도( 현재 키 높이: 인원(1) )을 담고 다음 정보를 입력받는다.

크게 두 가지 경우로 나뉜다.

1. top의 키높이가 현재 키높이와 같은 경우  -> top의 인원수만큼 쌍으로 추가

2. top의 키높이보다 현재 키높이가 큰 경우 -> 인접한 경우이므로 쌍으로 추가

위 두 가지 경우는 top의 키높이가 현재 키높이보다 클 때까지 혹은 스택이 빈상태가 될 때까지 pop 연산을 수행한다.

pop 연산을 수행한 이후에 스택이 비어있지 않다면 top에 해당하는 키와 현재 키와는 인접한 경우이므로 쌍으로 추가할 수 있다.

키높이가 같은 경우를 거쳤다면 (현재 키높이 : 추가했던 인원수+1) 형태로 스택에 추가.

그렇지 않았다면 (현재 키높이 : 인원수 1) 형태로 스택에 추가하면 된다.

즉 스택이 top으로 갈수록 내림차순을 유지하면 서로 바라볼 수 있는 쌍을 알아낼 수 있다.

정답 코드

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

구현문제다. 입력되는 경사로의 정보를 어떻게 탐색할지 고민했다.

풀이

입력되는 경사로의 정보를 ( 높이(숫자), 길이(연속되는 갯수) ) 형태의 튜플을 담는 배열로 정리하여 탐색을 수행한다.

다음과 같은 조건을 확인하여 갯수를 추가하였다.

• 현재 위치와 다음 위치와의 높이 차이가 1 이어야 한다.
• 다음 경사로의 높이가 더 높은 경우라면 현재 위치의 길이를 확인한다.
• 현재 경사로의 높이가 더 높은 경우라면 다음 위치의 길이를 확인한다.
• 만약 경사로를 놓아야 하는 위치에 처음 경사로가 설치되는 경우라면 해당 위치의 길이가 L 이상인지 확인한다.
• 만약 경사로를 놓아야 하는 위치에 경사로가 이미 설치된 경우라면 해당 위치의 길이가 2*L 이상인지 확인한다.

정답 코드

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

구현 문제다. 특정 알고리즘보단 문제에 어떻게 접근해야 할지 고민해 보게 되는 유형이다.

풀이

입력된 벽의 높이를 좌에서 우로 탐색한다. (탐색값 중 가장 높은 높이 - 현재높이) 값을 임시 변수에 누적. 가장 높은 높이가 갱신되면 여태 구한 임시 변수의 값을 최종 정답에 반영. 새로 바뀐 최대 높이를 기준으로 다시 빗물을 계산한다. 

탐색이 끝나고 임시 값을 최종 정답에 반영하지 못했다면, W-1번부터 마지막으로 갱신된 가장 높은 높이의 벽까지 역탐색하며 빗물을 계산하면 된다.

정답 코드

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

다익스트라 알고리즘 문제다. 런타임 에러를 만나 고생했다.

풀이

접근방법에 대해 간략하게 이야기하면 다음 흐름과 같다.

1. 다익스트라 알고리즘을 통해 시작노드 S부터 각 노드까지의 최단거리를 구해놓은 뒤,
2. 도착노드 D부터 시작노드 S까지 그래프 탐색을 통해 해당 경로가 최단경로임이 확인되면 해당 경로를 삭제
   (여기서 1에서 구한 최단경로 비용이 사용된다.)
3. 최단 경로가 삭제된 상태의 그래프를 다익스트라 알고리즘을 수행하여 거의 최단 경로를 구해내면 된다.

2번 과정이 이번 문제의 핵심이라고 생각한다. 우선 그래프가 방향이 정해져 있는 지향그래프이기에, 그래프 탐색을 위해 간선정보를 입력받을 때, 역탐색을 위한 rev배열을 생성하여 따로 저장해 놓는다. 배열의 경우 [[(node:Int, cost:Int)]]() 형태의 튜플 배열로 저장하여 다음 노드의 번호와 비용을 저장.

D -> S 역탐색을 수행할 때, 해당 경로가 최단경로임을 확인하는 방법은 다음과 같다. 여기서 1번 과정에서 구한 최단비용이 사용된다.

(D에서 해당 노드까지의 탐색비용 + S에서 해당 노드까지의 최단 비용) == (S에서 D까지의 최단비용)

여기서 최단경로임이 확인되면, 해당 경로를 삭제한 뒤 해당노드에서 다음 탐색을 이어가면 된다. 경로 삭제를 표현하는 방법은 많겠지만, 본인의 경우 해당 노드의 인덱스를 -1로 수정하여 삭제된 경로임을 표시하였다.

이후 수정된 그래프를 기준으로 다익스트라 알고리즘을 수행하면 거의 최단 경로를 구할 수 있다.

주의할 점

8%에서 런타임 에러를 뿜어대길래 반례를 찾느라 헤맸다. 다익스트라 알고리즘을 수행할 때, INF를 생각 없이 Int.max로 설정하여 오버플로우가 발생했었다. 즉 1번에서 얻은 최단 경로값에 Int.max가 있었고, 이걸 2번 과정에서 최단경로인지 확인할 때, D에서 해당 노드의 탐색비용 + Int.max의 연산이 수행되니 오버플로우가 발생했던 것. 따라서 (N의 최댓값 500 * 비용의 최댓값 1,000) 여기에 조금 더 여유를 둬서 INF를 5,000,000으로 설정하여 다익스트라를 수행하였더니 통과하였다. 백준의 경우 스위프트는 어떤 오류던지 무조건 런타임 에러를 반환하기에 원인을 찾는데 조금 고생했다. 그래도 이렇게 힘들게 문제를 해결하면 성취감이 몰려온다. 이런 매력에 PS를 하는 게 아닌가 싶다.

정답 코드