Hyun's_Devlog

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

그래프 탐색 문제. 시간초과를 해결하지 못해 결국 풀이를 찾아보았다.

풀이 방법

배열 범위 밖으로 탈출할 수 있는 노드의 수를 반환해야 한다.

단순히 깊이우선으로 모든 노드에 수행하게 되면 시간초과가 일어난다.

미로의 각 칸에서 넘어가는 다음 칸은 지정되어 있다. 따라서 이미 탐색을 수행한 노드의 끝이 맵 밖으로 이어지는지,  아니면 맵을 탈출 하지 못하고 사이클을 형성하는지 미리 저장해 둔다면 시간 내에 정답을 반환할 수 있다.

미로와 같은 크기의 N*M 2차원 visited 배열 생성. 특정 좌표를 아직 탐색하지 않았다면 -1, 해당 좌표가 탈출하지 못하는 좌표라면 0, 미로를 탈출할 수 있는 좌표라면 1을 저장한다.

깊이 우선 탐색을 수행. 다음 좌표가 미로 밖이라면 1 반환. 아닌 경우에는 처음 방문 좌표인지 확인하여 처음 방문 하는 곳이라면 (-1) 다음 좌표로 재귀호출이 이루어지며 해당 좌표에 결괏값이 저장된다. 

탐색을 통해 1의 개수를 정답으로 출력하면 된다.

정답 코드

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

최단거리 탐색 알고리즘으로 접근한 문제다. 

풀이

특정 정점에서 다른 정점까지의 최단거리를 계산하는 다익스트라 알고리즘을 사용했다. 이때 핵심은 주어지는 T의 범위가 40,000이라는 점이다. 즉 매 연습마다 40,000번의 그래프 탐색이 일어난다면 시간초과로 이어진다.

정점의 개수 N이 최대 300이며 간선의 최대 개수는 25,000인 점을 고려한다면 이전에 사용했던 정보가 중복으로 요구된다는 합리적인 결론에 도달한다.

따라서 다익스트라 알고리즘을 구현한 뒤 결과 값을 저장할 수 있는 <시작점, 각 정점까지의 최단거리> 형태의 딕셔너리를 생성하여 이전에 요구한 적 없는 시작점이 주어진다면 다익스트라 알고리즘을 통해 해당 결과를 저장한다. 반대로 이전에 요구한 적이 있던 시작점이라면 해당 시작점으로부터의 최단거리 정보는 이미 저장되어 있으므로 바로 출력이 가능하다.

즉 매 횟수마다 최단거리를 계산할 경우 O(4,000 * 25,000)의 시간복잡도로 인해 시간초과가 일어나겠지만, 모든 정점에서 다익스트라 알고리즘을 미리 수행한 결과를 이용한다면 O(300 * 25,000)의 시간복잡도로 시간 단축이 가능하다는 얘기다.

정답 코드

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

기본적인 MST 문제다. 

풀이

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

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

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

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

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

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

정답 코드-1

정답 코드 - 2

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를 하는 게 아닌가 싶다.

정답 코드