Jenikeju

import Foundation

// 입력받기
let T = Int(readLine()!)!

for i in 0..<T {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let N = input[0], M = input[1]
    var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
    var queue = [(idx: Int, ipt: Int)]()
    var count = 0
    for j in 0..<arr.count {
        queue.append((idx: j, ipt: arr[j]))
    }
    // 궁금한 문서 뽑을때까지 반복
    while true {
        if isImportant(queue) {
            count += 1
            if pop(&queue).idx == M { break }
        } else {
            moveBack(&queue)
        }
    }
    print(count)
}

// 첫번째원소가 중요도가 가장 높은지 파악
func isImportant(_ queue: [(idx: Int, ipt: Int)]) -> Bool {
    guard let top = top(queue) else { return false }
    var max = Int.min
    for i in queue {
        if i.ipt > max { max = i.ipt }
    }
    if max == top.ipt { return true } else { return false }
}
// 첫번째 원소 출력
func top(_ queue: [(idx: Int, ipt: Int)]) -> (idx: Int, ipt: Int)? {
    if queue.isEmpty { return nil }
    return queue[0]
}
// 첫번째 원소 Pop
func pop(_ queue: inout [(idx: Int, ipt: Int)]) -> (idx: Int, ipt: Int) {
    var a = Array(queue.reversed())
    let num = a.removeLast()
    queue = Array(a.reversed())
    return num
}
// 첫번째 원소 뒤로 이동
func moveBack(_ queue: inout [(idx: Int, ipt: Int)]) {
    let num = pop(&queue)
    queue.append(num)
}

내가 푼 풀이

접근방법: 이분탐색

이전에 두용액문제를 풀고왔더니 너무 쉽게 파악해버렸다

두 용액을 섞을땐 용액의수가 최대 10만이였는데 이 문제에선 최대 5000 이다.

단순히 두 용액을 고정하고 한 용액을 순회하며 섞어봐도 정답은 나오지만 5000^3 = 1250억번 연산이므로 시간초과가 무조건 뜰것이다.

그래서 두개의 용액을 고정하고 한 용액을 구할때 이분탐색을 이용했다.

시간복잡도는 O(N^2logN)으로 이문제에선 약 9700만번연산(1억보다 적다)으로 시간안에 풀어졌다.

이분탐색

용액을 섞었을때, 음수면 start인덱스가 mid+1 양수면 end인덱스가 mid-1 해주어 0과 가장 가깝게 만든다.

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var minSum = Int.max
var answer = [Int]()
// 이분탐색 사용을위해 정렬
arr.sort(by: <)


// 이분탐색
for i in 0..<N {
    for j in i+1..<N {
        // 두용액을 고정한다.
        let first = arr[i]
        let second = arr[j]
        let sum = first + second
        var s = j+1
        var e = N-1
        // 나머지 한용액을 이분탐색을 이용해 구해준다.
        while s <= e {
            let m = (s+e)/2
            let total = sum + arr[m]
            // 0이되면 바로 값 갱신 후 탈출
            if total == 0 {
                answer = [arr[i],arr[j],arr[m]]
                minSum = total
                break
            }
            // 합쳐진 용액이 음수면 나머지 용액을 더 큰수로, 양수면 더 작은수로
            if total < 0 {
                s = m+1
            } else {
                e = m-1
            }
            // 최솟값이 나오면 항상 값을 갱신해준다.
            if minSum > abs(total) {
                minSum = abs(total)
                answer = [arr[i],arr[j],arr[m]]
            }
        }
        
    }
}

print("\(answer[0]) \(answer[1]) \(answer[2])")

내가 푼 풀이

접근방법: 플로이드 워셜 알고리즘

- 플로이드 워셜 알고리즘을 이용해 모든노드쌍의 최단거리를 구한다.

- 이때 최댓값과, 출력할때 갈수 없는경우를 0출력하는것을 주의한다.

import Foundation

// 입력
let n = Int(readLine()!)!
let m = Int(readLine()!)!
var graph = Array(repeating: Array(repeating: 1000000000, count: n+1), count: n+1)

// 인접행렬
for _ in 0..<m {
    let bus = readLine()!.split(separator: " ").map{Int(String($0))!}
    if graph[bus[0]][bus[1]] > bus[2] {
        graph[bus[0]][bus[1]] = bus[2]
    }
}
// i도시는 i도시로 갈 수 없다.
for i in 1...n {
    graph[i][i] = 0
}

// 플로이드-워셜 알고리즘
for m in 1...n {
    for i in 1...n {
        for j in 1...n {
            let im = graph[i][m]
            let mj = graph[m][j]
            graph[i][j] = min(graph[i][j], graph[i][m] + graph[m][j])
        }
    }
}

// 최단거리를 구하기위해 비교값으로 큰 값을 주었는데, 이동할 수 없음을 0으로 변환
for i in 0..<graph.count {
    for j in 0..<graph[0].count {
        if graph[i][j] == 1000000000 { graph[i][j] = 0 }
    }
}

// 출력
for i in 1..<graph.count {
    var answer = ""
    for j in 1..<graph[i].count {
        if j == graph[i].count - 1 {
            answer += "\(graph[i][j])"
        } else {
            answer += "\(graph[i][j]) "
        }
    }
    print(answer)
}

다익스트라 알고리즘을 이용하여 선형탐색을 한다면, 시간초과가 난다.

따라서 다익스트라 알고리즘을 이용하되, 최단거리가 가장 짧은(여기선 루피가 적은)것 먼저 우선순위로 고른다.

현재 위치에서 상하좌우로 이동가능하니, 현재위치의 인접한노드는 상하좌우로 한다.

코드로 구현하면 다음과 같다.

import Foundation

var index = 1
while true {
    // 입력받기
    let N = Int(readLine()!)!
    if N == 0 { break }
    var graph = [[Int]]()
    var md = Array(repeating: Array(repeating: 1000000, count: N), count: N)
    for i in 0..<N {
        graph.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    }
    md[0][0] = graph[0][0]
    var queue = [(x: 0, y: 0, cost: graph[0][0])]
    var dx = [0,1,0,-1]
    var dy = [1,0,-1,0]
    
    // 다익스트라
    while !queue.isEmpty {
        let node = queue.removeLast()
        // 맨 오른쪽아래에 도달하면 멈춤
        // 최단거리가 가장 적은것 우선순위로 탐색하기때문에, 멈춰도된다. 선형탐색이라면 정답이 아닐수도 있다.
        if node.x == N-1 && node.y == N-1 { break }
        // 인접한 위치들 선택
        for i in 0..<4 {
            let mx = node.x + dx[i]
            let my = node.y + dy[i]
            if mx >= N || mx < 0 || my >= N || my < 0 { continue }
            if md[my][mx] > md[node.y][node.x] + graph[my][mx]{
                md[my][mx] = md[node.y][node.x] + graph[my][mx]
                queue.append((x: mx, y: my, cost: md[my][mx]))
            }
        }
        // 큐의 우선순위를 루피가 가장적은것 우선(배열의 마지막을 뽑기때문에 내림차순으로 한다.)
        queue.sort{ $0.cost > $1.cost }
    }
    print("Problem \(index): \(md[N-1][N-1])")
    index += 1
}

문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

내가 푼 풀이

접근방법: 다익스트라

처음에 그래프를 저장할 때 인접행렬로 저장했다가, 30만 x 30만이라서  메모리 초과가 일어났다.

인접리스트로 그래프를 저장하고 다익스트라 알고리즘을 이용한다.

다익스트라는 선형탐색으로 하였지만 겨우 시간초과에 안맞게 통과된거같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1], K = input[2], X = input[3]
var md = Array(repeating: 1000000, count: N+1)
var graph = [Int: [Int]]()

// 인접리스트
for i in 0..<M {
    let road = readLine()!.split(separator: " ").map{Int(String($0))!}
    if graph[road[0]] == nil {
        graph[road[0]] = [road[1]]
    } else {
        graph[road[0]]!.append(road[1])
    }
}

var queue = [(cur: X, cost: 0)]
md[X] = 0
// 다익스트라
while !queue.isEmpty {
    let node = queue.removeLast()
    var next = graph[node.cur]
    // 그다음 인접노드가 없거나 이미 K보다 크다면 의미가 없으므로 건너뜀
    if next == nil || node.cost > K { continue }
    // 인접한 노드들의 최단거리정보를 저장하고, 다음 노드 탐색
    for i in next! {
        if md[i] > md[node.cur] + 1 {
            md[i] = md[node.cur] + 1
            queue.append((cur: i, cost:md[i]))
        }
    }
    
}

// 출력
var find = false
for i in 0..<md.count {
    if md[i] == K {
        find = true
        print(i)
    }
}

if !find {
    print(-1)
}

1. 주어진 버스들로 2차원 배열을 만든다 (arr[i][j]: i도시에서 j도시까지의 거리)

1-1. 출발지와 도착지가 동일한경우 더 작은값을 넣는다.

2. 최단거리를 저장할 배열을 만든다.

3. 다익스트라 탐색을 이용해 이동가능한 버스를 통해 최단거리를 갱신한다.

4. 최종 갱신된 최단거리 배열에서 도착점의 원소 출력

import Foundation

// 입력받기
let N = Int(readLine()!)!
let M = Int(readLine()!)!
var cities = Array(repeating: Array(repeating: Int.max, count: N+1), count: N+1)
var bus = [[Int]]()
for i in 0..<M {
    let b = readLine()!.split(separator: " ").map{Int(String($0))!}
    bus.append(b)
}
let direct = readLine()!.split(separator: " ").map{Int(String($0))!}

// 2차원 배열로 만들기 cities[i][j] : i도시에서 j도시로 가는 거리
// 출발지와 목적지가 동일한 버스가 주어진다면 값비교해서 최솟값만 넣기
for i in bus {
    if cities[i[0]][i[1]] == Int.max {
        cities[i[0]][i[1]] = i[2]
    } else {
        if cities[i[0]][i[1]] > i[2] {
            cities[i[0]][i[1]] = i[2]
        }
    }
    
}
// 최단경로를 저장해놓을 배열
var md = Array(repeating: Int.max, count: N+1)
md[direct[0]] = 0
var queue = [(cur: direct[0], cost: 0)]

// 탐색
while !queue.isEmpty {
    let node = queue.removeFirst()
    for i in 1...N {
        // 현재 도시와 인접도시가 버스를 통해 갈 수 있고, 저장된 최단거리보다 더 짧다면 갱신해주고, 큐에 삽입
        if cities[node.cur][i] != Int.max && md[node.cur] + cities[node.cur][i] < md[i] {
            md[i] = md[node.cur] + cities[node.cur][i]
            queue.append((cur: i, cost: md[i]))
        }
    }
}
print(md[direct[1]])