Hyun's_Devlog

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

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

풀이 방법

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

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

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

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

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

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

정답 코드

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

기본형태의 그래프탐색 문제. 단 지팡이의 사용여부라는 조건이 붙어있다.

풀이 방법

너비 우선 탐색으로 목적지까지 그래프 탐색을 시도한다. 중복 방문을 피하기 위한 visited 배열을 3차원으로 생성.

visited[0][X][Y] -> 지팡이를 사용하지 않은 상태로 x,y 좌표 탐색여부,

visited[1][X][Y] -> 지팡이를 사용한 상태로 x,y, 좌표 탐색여부를 나타낸다.

visited 배열을 통해 좌표 탐색을 수행하여 정답을 출력하면 된다.

목적지에 도달하지 못하면 -1을 반환해야한다는 조건을 까먹지 말고 제출하자.

정답 코드

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

최단거리 탐색 문제다. 다익스트라 알고리즘으로 접근했다.

풀이

접근 가능한 정점과 N-1번 정점을 이어주는 간선들만 저장했다.

swift에는 다른 언어들과 달리 Heap이 구현되어있지 않아서 일반적인 경우에는 일반 큐를 사용하여 매 순환마다 정렬 작업을 하여 탐색하였는데 이번 문제는 간선정보가 최대 300,000개가 주어지므로 Heap 구현이 필요했다.

그런데 마주한 시간초과. 질문게시판을 찾아보니 다익스트라 알고리즘의 원리를 잘 고민하면 우선순위 큐를 더 빠르게 탐색이 가능하다고 한다. 

우선 다익스트라 알고리즘은 비용이 낮은 순으로 정렬된 우선순위 큐를 탐색하여 매 순간 각 정점으로의 최소비용을 갱신하게 된다.

즉, [현재 정점의 최소비용 + 현재 정점에서 다음 정점까지의 비용] 계산을 통해 다음 정점의 최단거리 정보를 갱신하는데, 이때 우선순위 큐에서 꺼낸  현재 정점의 정보가 최소 비용이 아니라면 결국 다음 정점까지의 정보를 탐색할 필요가 없다는 얘기다.

따라서 매 탐색마다 최단거리 정보를 담고 있는 cost[curr]와 우선순위 큐에 담겨있는 curr.cost 와의 비교를 통해서 최단거리보다 큰 비용이라면 continue를 통해 시간단축이 가능하다.

정답 코드

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

정답 코드

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

동적 계획법 문제다.

풀이

동적 계획법을 기본으로 그래프탐색을 통해 접근해야 한다. 부모 노드가 얼리어답터라면 자식노드는 얼리어답터 여부와 상관없이 해당 부분의 부모와 자식에게는 아이디어 전파가 가능하다. 반대로 부모가 얼리어답터가 아니라면 자식은 반드시 얼리어답터 이어야 한다. 

두 개의 자식을 가진 부모노드가 얼리어답터가 경우 아이디어가 전파되려면 그림과 같은 4개의 경우의 수가 만들어진다. 해당 부분에서의 정답은 가장 첫 번째의 경우가 최소조건임을 알 수 있다. 

하지만 반대로 부모가 얼리어답터가 아닐 경우, 자식들은 모두 얼리어답터 이어야만 조건이 맞다. 즉 우리는 부모노드가 얼리어답터인지, 일반인인지의 경우를 따져 얼리어답터의 수를 계산할 수 있게 된다.

그래프는 다음과 같이 두 개의 값을 가지는 형태로 구현한다. 0번 인덱스에는 자신이 일반인일 경우 얼리어답터의 수, 1번 인덱스에는 자신이 얼리어답터일 경우 얼리어답터의 수. 처음에는 당연히 자기 자신만 얼리어답터인 경우로 1로 초기화되어 있다.

먼저 부모가 얼리어답터가 아닐 경우부터 살펴본다. 해당경우는 자식노드가 무조건 얼리어답터이어야 하기 때문에 자식의 수만큼 더해진 값이 얼리어답터의 최소 개수다.

하지만 부모가 얼리어답터인 경우, 자식이 얼리어답터의 여부와 상관없이 최솟값을 가져오면 조건이 성립된다.

parent[0] += child_0[1] + child_1[1]...child_N[1]
parent[1] += min(child_0[0],child_0[1]) + ... min(child_N[0],child_N[1]))

즉 모든 노드가 [0,1] 형태로 초기화되어있을 경우, 해당 점화식을 사용하여 리프 노드의 정보를 통해 루트 노드까지 최소 얼리어답터의 수를 구할 수 있게 된다.

예제의 경우 다음과 같은 형태로 결과가 나오며, 출력은 루트노드의 두 개의 값 중 최솟값을 출력하면 된다. 코드로 보는 것이 이해하기 더 쉽다.

정답 코드

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

그래프 탐색 문제다.

풀이

모눈종이의 가장자리에는 치즈가 없다. 즉 (0,0) 좌표부터 너비우선탐색을 수행하여 치즈를 마주치면 해당 좌표를 저장. 탐색도중 같은 좌표를 한번 더 마주하게 된다면 해당 치즈는 2변이 실내온도에 닿은 것으로 판정하여 녹은 것으로 판정한다. 좌표를 저장하고 탐색하는 데에 O(1)만에 탐색이 가능한 Set 자료구조를 사용하였다. 치즈의 개수가 0이 될 때까지 탐색을 수행. 반복이 일어난 횟수를 출력하면 된다.

정답 코드

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

다익스트라 알고리즘으로 접근한 문제다.

풀이

너비우선탐색을 수행한다. 다익스트라 알고리즘의 특성상 우선순위 큐를 사용해서 풀어야 하지만, 문제의 N값이 크지 않기에 배열을 정렬하여 풀어도 시간초과는 피할 수 있다. 스위프트의 경우 우선순위큐를 직접 구현해야하기에 귀찮다.

방문여부를 저장할 2차원 visited 배열, 각 좌표에 도둑루피의 값을 담을 2차원 map 배열과 해당좌표까지의 최저 cost를 담을 2차원 cost배열을 생성한다. cost 배열은 INF로 초기화한 뒤 탐색을 수행한다. 

x, y, cost 정보를 담아낼 배열을 생성한다. 배열에서 cost가 가장 작은 좌표를 먼저 방문하여 (현재 좌표의 cost + 인접배열의 cost값)을 계산하여 인접배열의 cost를 더 작은 값으로 갱신한다. 다음 탐색에 cost가 가장 작은 값을 방문해야 하니 매 반복문의 마지막에는 큐를 정렬해 준다.

탐색이 끝나면 목적지인 cost배열의 가장 마지막 값을 출력하면 된다.

정답 코드