도착노드 D부터 시작노드 S까지 그래프 탐색을 통해 해당 경로가 최단경로임이 확인되면 해당 경로를 삭제 (여기서 1에서 구한 최단경로 비용이 사용된다.)
최단 경로가 삭제된 상태의 그래프를 다익스트라 알고리즘을 수행하여 거의 최단 경로를 구해내면 된다.
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를 하는 게 아닌가 싶다.
출시된 앱의 업데이트를 위해 빌드하다가 마주한 오류다. 스택오버플로우에서 찾아보니 최근에 진행된 xcode 14.3 업데이트로 인해 발생한 오류이다.
해결법은 간단하게도 해당 프로젝트의 cocoadpods 디렉터리 내에 있는 frameworks.sh 파일 속 "readlink" 명령어를 "readlink -f" 라는 옵션명을 덧붙이면 해결이 된다. 본인의 경우 "프로젝트 디렉토리/Pods/Target Support Files/Pods-프로젝트명" 위치에 "Pods-프로젝트명-frameworks.sh" 이름으로 파일이 있었다.
readlink 명령어에 대해 궁금해져서 찾아보았더니 유닉스 명령어로, 심볼릭 링크의 값을 출력하는 명령어이다. 7가지 옵션이 있는 것으로 나오는데, 각 옵션과 역할은 다음과 같다.
-f, --canonicalize : 심볼릭 링크의 원본 위치를 출력한다.
-n, --no-newline : 새로운 라인은 출력하지 않는다.
-q, --quiet, : 메시지를 출력하지 않는다.
-s, --silent : 대부분 에러 메시지를 출력하지 않는다.
-v, --verbose : 상세한 정보를 출력한다.
--help : 사용법을 출력한다.
--version : 버전 정보를 출력한다.
-f 명령어, 즉 심볼릭 링크의 원본 위치 참조를 통해 해결된 것을 보니 xcode 14.3 업데이트 항목에 cocoapods와의 연동과정에 필요한 경로 변경이 일어나 발생한 오류로 추정이 된다.
혹시나 해서 -f 명령어를 지우고 cocoapods를 업데이트해보았는데도 동일한 오류가 발생한 것을 보니 아직 cocoapods 측의 업데이트 대응이 진행 중인 것으로 보인다.
들어오는 좌표 중 3개를 선택하는 조합 반복문을 생성. 피타고라스의 정리를 사용해 직각 삼각형인지 판별하면 된다.
단 해당 문제에서 흥미로웠던 점은 세 점 A, B, C의 조합에서 나온 3가지의 선분(AB, BC, AC) 중 가장 긴 선분을 찾아내는 부분에서 시간초과가 났다.
처음에는 단순히 3개의 선분의 길이를 배열에 담아낸 뒤 내림차순 정렬하여 (0번 원소 == 1번 원소 + 2번 원소) 조건문으로 판별하였으나, 시간초과가 발생.
func isRightTriangle(a:(Int,Int),b:(Int,Int),c:(Int,Int)) -> Bool{
let AB = ((a.0-b.0)*(a.0-b.0)) + ((a.1-b.1)*(a.1-b.1))
let AC = ((a.0-c.0)*(a.0-c.0)) + ((a.1-c.1)*(a.1-c.1))
let BC = ((b.0-c.0)*(b.0-c.0)) + ((b.1-c.1)*(b.1-c.1))
let tmp = [AB,AC,BC].sorted(by: >)
return tmp[0]==tmp[1]+tmp[2] ? true:false
}
이때부터 조금 헤맸다. 시간복잡도를 계산해 보면 입력좌표는 최대 1500개가 입력. 1500C3 = 561,375,500 여기서 각 조합마다 정렬이 이루어지는데, Swift 배열의 정렬 함수 시간복잡도는 0(N)이므로 대략 16억 번의 수행이 이루어진다. 보통 알고리즘 문제를 풀 때 러프하게 1초당 1억 번의 연산으로 계산하게 되는데, 5초의 시간은 턱없이 부족한 시간인 것이다.
그러다 문득 배열을 생성하고 정렬하는 것보단 비트연산이 더욱 빠르겠다는 생각이 들어 아래와 같이 수정하였더니 통과하였다.
func isRightTriangle(a:(Int,Int),b:(Int,Int),c:(Int,Int)) -> Bool{
let AB = ((a.0-b.0)*(a.0-b.0)) + ((a.1-b.1)*(a.1-b.1))
let AC = ((a.0-c.0)*(a.0-c.0)) + ((a.1-c.1)*(a.1-c.1))
let BC = ((b.0-c.0)*(b.0-c.0)) + ((b.1-c.1)*(b.1-c.1))
// let tmp = [AB,AC,BC].sorted(by: >)
// return tmp[0]==tmp[1]+tmp[2] ? true:false
let res = (AB==AC+BC) || (AC == AB+BC) || (BC==AB+AC)
return res ? true:false
}
해당 문제의 컴퓨터는 자료를 전송할 다음 등급의 컴퓨터가 여러 대라면 동시에 자료를 전송하는 것으로 계산하면 된다. 즉 위상정렬을 통해 다음 등급의 컴퓨터를 탐색할 때, 간선의 비용이 최대 값인 경우만 찾아내면 된다.
입력되는 등급을 통해 위상정렬 순서를 구해 탐색을 수행한다. (다음 등급의 컴퓨터에게 자료를 전달하는 시간 + 다음 컴퓨터의 구동시간)의 최댓값을 저장할 ans 배열을 생성. 매 탐색마다 해당 배열을 최댓값으로 갱신하고 탐색이 종료된 후 ans 배열의 최댓값을 출력하면 정답이다.
예제를 기준으로 다음과 같이 수행된다.
가장 먼저 가장 낮은 등급의 컴퓨터인 1번과 7번 컴퓨터가 동작한다.
각자의 (동작시간 + 전송시간)의 값 중 가장 큰 값이 다음 등급인 6번 컴퓨터에게 전달되며,
해당 컴퓨터는 자신의 구동시간을 더해 ans배열에 갱신한다.
이후 탐색 큐에 6과 ans [6]의 값 36을 담아 다음 탐색을 수행한다.
2등급 컴퓨터인 6번 노드는 다음 등급의 컴퓨터인 2번과 3번 컴퓨터에 자료를 전송.
6번 컴퓨터의 대기시간 + 동작시간의 값 + 전송시간의 값이 전달된다.
이제 해당 값에 2번과 3번 컴퓨터의 구동시간을 더해 ans배열을 갱신한다.
각 노드로 진입하는 대기시간 + 구동시간 + 전송시간의 값 중 가장 큰 값을 입력받아 ans배열을 갱신해 나가면 된다.
구동시간에는 음수가 입력되지 않으므로 마지막 컴퓨터의 대기시간 + 구동시간 + 동작시간을 더해 출력하면 된다.
사이클이 생기는 노드, 그리고 해당 노드로 진입하는 노드를 제외한 나머지 노드의 수를 출력하는 문제다.
주어지는 간선의 방향을 반대로 저장하고 위상정렬을 통해 탐색한다면, 정답을 구할 수 있다. 이유는 위상정렬의 필수조건인 indegree가 0인 노드를 큐에 담아 탐색하는 부분에서 찾을 수 있다. 사이클이 발생한다는 것은 곧 indegree가 0이 되지 않는다는 이야기이기에 역방향으로 탐색하게 되면 사이클은 큐에 담기지 않게 된다.
예제의 경우를 그래프로 그려보면 좌측과 같다. 위상정렬을 통해 탐색을 시작하면 1부터 시작하기에 처음부터 사이클이 일어날지 알 수 없다. 반면 우측의 경우처럼 역방향으로 그래프를 그리면 4와 6만 큐에 담긴 채 사이클이 일어나는 3번 노드는 큐에 담기지 않게 되고 그대로 탐색이 종료된다. 따라서 정답은 4, 6번 학생인 두 명의 부원이라는 정답을 출력할 수 있다.
