Jenikeju

    +---+        
    | D |        
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |        
    +---+        

내가 푼 풀이

- 주어진 n^3개의 주사위를 적당히 회전시켜서 쌓아 올린 n * n * n크기의 정육면체를 만들때의 보이는 5개면의 합 최솟값을 구한다.

- 바닥과 마주본 면은 보이지 않으므로 합에서 제외된 5개의 면이다.

- 주사위를 쌓아올렸을때, 보이는 면의개수의 경우의 수는 3가지이다.

- 주사위의 3개의 면이 보이는경우, 2개의 면이 보이는 경우, 1개의 면이 보이는 경우 이다.

- 해당 3가지 경우의수 모두 최솟값으로 구한다면, 쌓아 올린 정육면체의 5개면의 합이 최솟값이 된다.

- 처음에는 노가다로 주사위의 면 하나를 기준으로 했을 때, 3개의 면이 보이는 경우의 수를 모두 구하고, 중복되는 값을 소거했다.

- 2개의 면을 구할때도 모든 경우의 수를 구하고 중복된 경우의 수를 제거하여서 구한 값 중 최솟값을 구했다.

- 3가지 경우의 수를 구했다면 n * n * n 의 정육면체에서 이전에 경우의 수가 몇 개나 구성되어 있는지 파악한다.

• 3개의 면이 보이는 주사위 개수 : 4개
• 2개의 면이 보이는 주사위 개수 : 4 * (N-1) + 4 *(N-2)
• 1개의 면이 보이는 주사위 개수: 4 * (N-1) * (N-2) + 4 * (N-2)^2

모든 경우의수를 노가다로 구했을 때의 코드는 다음과 같다.

let n = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
var num3 = [Int]()
var num2 = [Int]()

// ABC ABD ACE ADE
// BDF BCF CEF DEF
num3 = [arr[0] + arr[1] + arr[2],
        arr[0] + arr[1] + arr[3],
        arr[0] + arr[2] + arr[4],
        arr[0] + arr[3] + arr[4],
        arr[1] + arr[3] + arr[5],
        arr[1] + arr[2] + arr[5],
        arr[2] + arr[4] + arr[5],
        arr[3] + arr[4] + arr[5]
        ]

// AB AC AD AE
// BC BD BF CF
// CE DE DF EF
num2 = [arr[0] + arr[1],
        arr[0] + arr[2],
        arr[0] + arr[3],
        arr[0] + arr[4],
        arr[1] + arr[2],
        arr[1] + arr[3],
        arr[1] + arr[5],
        arr[2] + arr[5],
        arr[2] + arr[4],
        arr[3] + arr[4],
        arr[3] + arr[5],
        arr[4] + arr[5]
        ]

var num3Min = num3.min()!
var num2Min = num2.min()!
var num1Min = arr.min()!

if n == 1 {
    print(arr.reduce(0, +) - arr.max()!)
} else {
    print(num3Min * 4 + num2Min * ((n-1) * 4 + (n-2) * 4) + num1Min * (4 * (n-1) * (n-2) + (n-2) * (n-2)))
}

해당 코드는 정답이 떴지만 주사위의 원리를 좀 이용해보려 한다.

A와 마주 보는 면은 F

B와 마주보는면은 E

C와 마주보는면은 D이다.

3면이 보이는 주사위를 회전시켜서 보일 때, 각 보이는 면과 마주 보는 면은 같이 보일 수 없다.

따라서 3면이 보이는 숫자를 최소로 만들려면 위의 세 가지를 모두 더한 값을 최솟값으로 만들면 된다.

2면이 보이는 주사위도 마찬가지로 위에 세 가지 중 작은 두 가지를 더한 값이 최솟값이 된다.

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

import Foundation

let n = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }

var min1 = min(arr[0], arr[5])
var min2 = min(arr[1], arr[4])
var min3 = min(arr[2], arr[3])

var sortedArr = [min1, min2, min3].sorted{ $0 < $1}
var num1Min = sortedArr[0]
var num2Min = sortedArr[0] + sortedArr[1]
var num3Min = sortedArr[0] + sortedArr[1] + sortedArr[2]


if n == 1 {
    print(arr.reduce(0, +) - arr.max()!)
} else {
    var result = 0
    result += num3Min * 4
    result += (num2Min * (n-1) * 4 + num2Min * (n-2) * 4)
    result += (num1Min * (n-1) * (n-2) * 4 + num1Min * (n-2) * (n-2))
    print(result)
}

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

내가 푼 풀이

- 문제 내려가기 게임의 원리 자체도 쉬워서 구현도 쉬웠다.

- 내려가기의 원리를 반대로 생각하면

첫 번째 원소는 이전의 첫 번째와 두 번째 원소로부터

두 번째 원소는 이전에 모든 원소로부터

세 번째 원소는 이전에 두 번째와 세 번째 원소로부터 더해지는 것이다.

- 3 크기의 dp배열을 선언해서 이전의 값을 저장하고 이후에 나오는 원소들과 더해서 최댓값, 최솟값을 저장해서 출력한다.

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

import Foundation

let count = Int(readLine()!)!
var maxDp = Array(repeating: 0, count: 3)
var minDp = Array(repeating: 0, count: 3)

// DP 입력
// 이전의 값과 새로 추가되는 원소와 더해서 최대값 최소값을 넣는다.
for i in 0..<count {
    let arr = readLine()!.split(separator: " ").map{ Int($0)! }
    if i == 0 {
        maxDp = arr
        minDp = arr
        continue
    }
    let dp1 = maxDp
    let dp2 = minDp
    maxDp[0] = max(arr[0] + dp1[0], arr[0] + dp1[1])
    maxDp[1] = max(arr[1] + dp1[0], arr[1] + dp1[1], arr[1] + dp1[2])
    maxDp[2] = max(arr[2] + dp1[1], arr[2] + dp1[2])
    
    minDp[0] = min(arr[0] + dp2[0], arr[0] + dp2[1])
    minDp[1] = min(arr[1] + dp2[0], arr[1] + dp2[1], arr[1] + dp2[2])
    minDp[2] = min(arr[2] + dp2[1], arr[2] + dp2[2])

}

print("\(maxDp.max()!) \(minDp.min()!)")

내가 푼 풀이

- 주어진 연결된 두 정점을 연결리스트로 저장한다.

- 트리의 루트는 1 이므로 1부터 인접한 곳을 탐색한다.

- 이때 인접한 곳의 부모노드는 이전에 탐색된 노드의 번호가 되는 것이다.

- 인접한 노드 중 이미 탐색한 곳을 제외하고 새롭게 인접한 곳을 탐색한다.

- 부모노드를 배열에 따로 저장하고 출력

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

import Foundation

// 부모노드배열, 트리 연결리스트
let count = Int(readLine()!)!
var tree = [Int: [Int]]()
var parent = Array(repeating: 0, count: count+1)

// 연결리스트 입력
for i in 0..<count-1 {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    if tree[input[0]] == nil {
        tree[input[0]] = [input[1]]
    } else {
        tree[input[0]]!.append(input[1])
    }
    if tree[input[1]] == nil {
        tree[input[1]] = [input[0]]
    } else {
        tree[input[1]]!.append(input[0])
    }
}

// 시작점은 루트노드 1
var needVisitQueue = [1]

// BFS
// 인접한 노드 탐색
// 이미 탐색한 곳은 제외하고 새롭게 탐색한다.
// 인접한 노드의 부모노드는 이전에 탐색된 노드번호가 된다.
while !needVisitQueue.isEmpty {
    var node = needVisitQueue.removeLast()
    var arr = [Int]()
    for i in tree[node]! {
        if parent[i] == 0 && i != node {
            parent[i] = node
            arr.append(i)
        }
    }
    needVisitQueue += arr
}

// 부모노드 출력
for i in 2...count {
    print(parent[i])
}

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

원소 7)

원소 5)

원소 4)

원소 2)

이렇게 정렬된 배열은 인접한 통나무의 높이 차가 최소가 된 배열이 된다.

해당 통나무 건너뛰기 난이도는 인접한 차이중 최대가 되는 9-5 = 4 가된다.

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

import Foundation

// 테스트케이스 수
let c = Int(readLine()!)!

for i in 0..<c {
    // 주어진 통나무 수 와 높이 배열 입력
    let count = Int(readLine()!)!
    var arr = readLine()!.split(separator: " ").map{ Int($0)! }
    
    // 오름차순
    var sortedArr = arr.sorted{$0 < $1}
    
    // 배열 정렬
    var max = sortedArr.removeLast()
    var arr1 = [Int]()
    var arr2 = Array(repeating: 0, count: sortedArr.count / 2)
    var idx = 0
    while idx < sortedArr.count {
        if idx+1 == sortedArr.count {
            arr1.append(sortedArr[idx])
            idx += 1
        } else {
            arr1.append(sortedArr[idx])
            arr2[arr2.count-1-(idx/2)] = sortedArr[idx+1]
            idx += 2
        }
    }
    arr1.append(max)
    var r = arr1 + arr2
    
    // 인접한 통나무의 높이차이를 비교하여 가장 큰 차이를 저장
    var min = -1
    for j in 0..<r.count {
        var num = Int()
        if j == r.count - 1 {
            num = r[j] - r[0]
        } else {
            num = r[j] - r[j+1]
        }
        if min < abs(num) { min = abs(num) }
    }
    print(min)
}

문제

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가로

세로

대각선

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

- 해당 문제를 봤을때 dfs로 풀 수 있을 정도의 크기지만, dp로 풀어보도록 했다.

- dp로 푸는경우에는 세가지의 경우를 생각해야했다.

- 가로로 가는방향, 세로로 가는방향, 대각선으로 가는방향 세가지를 3차원배열로 저장한다.

- dp[n][n] = (n,n) 까지 가는 경우의 수 라고 한다면, 2차원 배열로 입력했을때, 가로로 뻗어있을때 세로로 갈 수 없는 경우의 수까지 세게된다.

- dp[가로][n][n] , dp[세로][n][n], dp[대각선][n][n]으로 정의하여 현재 위치에서 가로 세로 대각선으로 갈 수 있다면 해당 배열의 위치에 dp값을 저장하고 세가지방법을 모두 더한다.

- 맨 처음 파이프는 (0,0) 에서 (0,1)로 가로로 뻗어있다.

- 파이프를 놓는 원리는 단순했지만, 원리안에 있는 조건을 dp입력할때 이용하는게 어려웠다.

import Foundation

let n = Int(readLine()!)!
var arr = [[Int]]()
var dp = [[[Int]]]()

for i in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

// 3차원 dp 선언
// 가로: 0, 세로: 1, 대각선: 2
for i in 0..<3 {
    var a = [[Int]]()
    dp.append(Array(repeating: Array(repeating: 0, count: n), count: n))
}

// 처음 파이프는 (0,0) 에서 (0,1)로 놓여져있다.
dp[0][0][1] = 1

// 파이프를 놓을 수 있는 조건에 맞게 dp값 입력
for i in 0..<n {
    for j in 0..<n {
        if i == 0 && j == 0 { continue }

        if j+1 < n && arr[i][j+1] == 0 {
            dp[0][i][j+1] += dp[0][i][j]
            dp[0][i][j+1] += dp[2][i][j]
        }
        if i+1 < n && arr[i+1][j] == 0 {
            dp[1][i+1][j] += dp[1][i][j]
            dp[1][i+1][j] += dp[2][i][j]
        }
        if i+1 < n && j+1 < n && arr[i+1][j] == 0 && arr[i][j+1] == 0 && arr[i+1][j+1] == 0 {
            dp[2][i+1][j+1] += dp[0][i][j]
            dp[2][i+1][j+1] += dp[1][i][j]
            dp[2][i+1][j+1] += dp[2][i][j]
        }
    }
}

print(dp[0][n-1][n-1] + dp[1][n-1][n-1] + dp[2][n-1][n-1])

내가 푼 풀이

- 비가 아예오지않는 경우 높이가 0 일 때부터 비가 최대치로 오는 경우 높이가 배열의 자연수중 가장 높은 수 까지 조사한다.

- 조사할때 인접한 경우는 배열의 상하좌우가 붙어있다면 인접한 경우로 본다.

- BFS로 비가 오는 높이보다 높은 안전지역을 모두 탐색한다면 안전영역의 개수를 카운트해준다.

- 카운트한 개수는 최댓값을 항상 갱신해 준다.

import Foundation

let n = Int(readLine()!)!
var arr = [[Int]]()
var max = 0
var result = 0
// 상하좌우 방향
var dx = [1,0,-1,0]
var dy = [0,1,0,-1]

// 주어진 N * N 배열 입력
// 높이의 최대값 저장
for i in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
    if max < arr[i].max()! {
        max = arr[i].max()!
    }
}

// BFS
// 비가 아예오지않는 0 부터 최대높이 max까지 오는 모든 경우의 수 조사
// 비의 높이보다 큰 안전한영역의 개수 카운트하고, 최대값 갱신
for i in 0...max {
    var needVisitQueue = [(x:Int, y: Int)]()
    var copy = arr
    var count = 0
    for j in 0..<n {
        for k in 0..<n {
            if copy[j][k] > i {
                needVisitQueue = [(x: k, y: j)]
                copy[j][k] = -1
                while !needVisitQueue.isEmpty {
                    var loc = needVisitQueue.removeLast()
                    
                    for m in 0..<4 {
                        var x1 = loc.x + dx[m]
                        var y1 = loc.y + dy[m]
                        
                        if (x1 >= 0 && x1 < n) && (y1 >= 0 && y1 < n) {
                            if copy[y1][x1] > i {
                                copy[y1][x1] = -1
                                needVisitQueue.append((x: x1, y: y1))
                            }
                        }
                    }
                }
                count += 1
            }
        }
    }
    
    if count > result {
        result = count
    }
}
print(result)

내가 푼 풀이

- 주가가 최대일때 팔면 최대이익이 생긴다.

- 이는 날이 지날수록 다음날이 이전날보다 주가가 높으면 매수한다.

- 이 방법으로 매수해서 최고점을찍어 다음날이 이전날보다 주가가 떨어질때, 매수했던 주식을 판매하는 방법을 이용했는데, 자꾸 틀렸다고 떴다.

- 아마 출력조건에서 부호있는 64bit 정수형으로 표현해야하고, 반례가 있어서 다른 방법을 이용했다.

- 오늘이 다음날보다 주가가 낮으면 무조건 주식을 사면되는데, 반대로 최고가를 찍은 날을 알고있다면 그 전날의 주식들이 최고가보다 낮다면 모두 차익을 남기고 팔면된다.

- 이는 주어진 주가를 배열로 입력하고, 역순으로 주식의 최고가를 갱신하여 이전날이 주가가 낮다면 차익이 생긴다는 얘기다.

import Foundation

// 테스트케이스 개수
let cc = Int(readLine()!)!

for i in 0..<cc {
    let count = Int(readLine()!)!
    var arr = readLine()!.split(separator: " ").map{ UInt64($0)! }
    var max: UInt64 = 0
    var result: UInt64 = 0
    
    // 역순으로 주가의 최고가보다 전날이 적으면 차익을 계속 더해준다.
    for j in (0..<count).reversed() {
        if arr[j] > max {
            max = arr[j]
        } else {
            result += (max - arr[j])
        }
    }
    print(result)
}

문제

서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.

이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.

 

위의 예시를 보자.

이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.

따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.

프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

내가 푼 풀이

- 해당문제를 처음에 접했을 때, 건물 하나를 짓기 위해 인접한 접점 중 출발접점들을 탐색하는 BFS 방법을 사용하였다.

- DP배열에 건물 짓는 시간을 넣어서 최댓값을 갱신하는 방법으로 했지만, 입력되는 간선의 수가 최대 100,000개에 건물의 개수가 1000 되므로 상당히 많은 입력을 감당할 수 없어서 시간초과가 떴다.

- 해당문제는 정렬 알고리즘 중 하나인 위상 알고리즘을 이용해서 푼다.

- 위상 알고리즘은 사이클이 존재하지 않는 방향그래프에서 사용되는데 각 접점에 도착하는 진입차수와 뻗어나가는 진출차수를 저장해 둔 뒤, 큐에 진입차수가 0인 접점을 넣어서 탐색한다.

- 해당접점과 연결돼있는 다른 접점의 진입차수를 -1시켜주며, 해당 접점의 진입차수가 0이 되면 큐에 넣어주는 방식이다.

- 자세한 위상정렬 알고리즘: https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting

-또한 이 문제는 많은 입력을 감당하기에 readLine 함수로는 시간초과가 뜬다.

- 좀 더 빠른 FileIO를 이용해서 풀었다

import Foundation

final class FileIO {
    private var buffer:[UInt8]
    private var index: Int
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]
        index = 0
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        
        return buffer.withUnsafeBufferPointer { $0[index] }
    }
    
    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true
        
        while now == 10
                || now == 32 { now = read() }
        if now == 45{ isPositive.toggle(); now = read() }
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }
        
        return sum * (isPositive ? 1:-1)
    }
    
    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()
        
        while now == 10
                || now == 32 { now = read() }
        
        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }
        
        return str
    }
}
let fileio = FileIO()
let count = fileio.readInt()

for i in 0..<count {
    let input = [fileio.readInt(), fileio.readInt()]
    var dp = Array(repeating: 0, count: input[0]+1)
    var needBuild = Array(repeating: Array(repeating: 0, count: 0), count: input[0]+1)
    var graph = [Int: [Int]]()
    var finalBuild = 0
    var fees = [0]
    var queue = [Int]()
    var degree = Array(repeating: 0, count: input[0]+1)
    
    // 각 건물당 소요되는 시간 배열
    for j in 0..<input[0] {
        fees.append(fileio.readInt())
    }
    
    // 해당 건물과, 건물을 지을 수 있는 다른 건물을 그래프배열에 저장
    for j in 0..<input[1] {
        let inp = [fileio.readInt(), fileio.readInt()]
        needBuild[inp[1]].append(inp[0])
        if graph[inp[0]] == nil {
            graph[inp[0]] = [inp[1]]
        } else {
            graph[inp[0]]!.append(inp[1])
        }
    }
    
    // 최종으로 지어야하는 건물의 번호
    finalBuild = fileio.readInt()
    
    // 탐색의 시작점, 위상정렬 알고리즘을 사용하기 위한 진입차수가 0인 건물의번호를 큐에 넣는다.
    for j in 1...input[0] {
        degree[j] = needBuild[j].count
        if needBuild[j].count == 0 {
            queue.append(j)
        }
    }
    var idx = 0
    
    // 위상정렬 알고리즘
    // 진입차수가 0인 건물을 큐에 넣는다.
    // 건물에서 뻗어나가는 다른 건물들의 진입차수를 -1 해준다.
    // 뻗어나간 다른건물들 중 진입차수가 0인 건물은 큐에 넣어준다.
    // 건물짓는 소요시간을 뻗어나간 다음 접점의 dp배열에 저장
    while idx < queue.count {
        var node = queue[idx]
        idx += 1
        dp[node] += fees[node]
        
        if graph[node] != nil {
            for i in graph[node]! {
                dp[i] = max( dp[i], dp[node])
                degree[i] -= 1
                if degree[i] == 0 {
                    queue.append(i)
                }
            }
        }
        
    }
    print(dp[finalBuild])
}