벨만 포드 알고리즘 - swift

youjean.tistory.com/25

2020 브랜디 코딩대회 '코드네임B' 후기 - swift

→ 브랜디 코테 후기를 올린 이전 포스팅

​

2020 브랜디 코딩대회 '코드네임B'의 3번 문제를 찾다가

이 알고리즘을 찾게 되었는데요

​

3번 문제의 답안(답)은 아래와 같습니다.

 

struct Edge {
    var e = 0
    var v = 0
    
    init(e: Int, v: Int) {
        self.e = e
        self.v = v
    }
}
    
let MAX = (39800 * 100) + 1 // 노선의 최대 개수 * 각 노선 당 최대 시간 + 1
var cycle = false // 지점에 도달할 수 있는지 여부

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0] // n개의 지점
let m = input[1] // m개의 경로

var edges = Array.init(repeating: Array<Edge>(), count: n+1) // edges[0]을 쓰지 않고 지점 1부터 시작하기 위해 n + 1을 함
var dist = Array.init(repeating: MAX, count: n+1)

for _ in 0..<m {
    
    let strABC = readLine()!.split(separator: " ").map { Int($0)! }
    let a = strABC[0] // 출발지점
    let b = strABC[1] // 도착지점
    let c = strABC[2] // 소모되는 시간
    
    edges[a].append(Edge(e: b, v: c))
}

dist[1] = 0

//사이클이 도는지 기준
for i in 1..<n+1 {
    //노드 선택
    for j in 1..<n+1 {
        //해당 노드에서 뻗어 나가는 간선을 추출
        for edge in edges[j] {
            if dist[j] != MAX && dist[edge.e] > edge.v + dist[j] { // 최소거리를 넣어야 함으로 작을때만
                dist[edge.e] = edge.v + dist[j]
                if i == n {
                    cycle = true
                    break
                }
            }
        }
    }
}

if cycle { // 무한 사이클
    print("bug")
} else {
    if dist[n] == MAX {
        print("bug")
    } else {
        print(dist[n])
    }
}

 

 

정확한 이해를 위해 아래와 같이 print문을 추가하여 출력하면

for i in 1..<n+1 {
    print("=====================")
    print("i: \(i)")
    
    for j in 1..<n+1 {
        for edge in edges[j] {
            
            print("\(dist[edge.e]) > \(edge.v) + \(dist[j])")
            print("\(dist[j] != MAX) \(dist[edge.e] > edge.v + dist[j])")
            
            if dist[j] != MAX && dist[edge.e] > edge.v + dist[j] { 
                dist[edge.e] = edge.v + dist[j]
                
                print("dist: \(dist)")
                
                if i == n {
                    cycle = true
                    break
                }
            }
        }
    }
}

 

 

 

 

예시 1

 

입력:

3 3

1 2 10

1 3 9

2 3 -3

 

출력:

7

 

중간 출력:

 

i: 1
3980001 > 10 + 0
true true
dist: [3980001, 0, 10, 3980001]
3980001 > 9 + 0
true true
dist: [3980001, 0, 10, 9]
9 > -3 + 10
true true
dist: [3980001, 0, 10, 7]
=====================
i: 2
10 > 10 + 0
true false
7 > 9 + 0
true false
7 > -3 + 10
true false
=====================
i: 3
10 > 10 + 0
true false
7 > 9 + 0
true false
7 > -3 + 10
true false

 

 

예시 2

 

 

입력:

5 5

1 2 1

2 3 -1

2 5 1

3 4 -1

4 2 -1

 

출력:

bug

 

중간 출력:

 

i: 1
3980001 > 1 + 0
true true
dist: [3980001, 0, 1, 3980001, 3980001, 3980001]
3980001 > -1 + 1
true true
dist: [3980001, 0, 1, 0, 3980001, 3980001]
3980001 > 1 + 1
true true
dist: [3980001, 0, 1, 0, 3980001, 2]
3980001 > -1 + 0
true true
dist: [3980001, 0, 1, 0, -1, 2]
1 > -1 + -1
true true
dist: [3980001, 0, -2, 0, -1, 2]
=====================
i: 2
-2 > 1 + 0
true false
0 > -1 + -2
true true
dist: [3980001, 0, -2, -3, -1, 2]
2 > 1 + -2
true true
dist: [3980001, 0, -2, -3, -1, -1]
-1 > -1 + -3
true true
dist: [3980001, 0, -2, -3, -4, -1]
-2 > -1 + -4
true true
dist: [3980001, 0, -5, -3, -4, -1]
=====================
i: 3
-5 > 1 + 0
true false
-3 > -1 + -5
true true
dist: [3980001, 0, -5, -6, -4, -1]
-1 > 1 + -5
true true
dist: [3980001, 0, -5, -6, -4, -4]
-4 > -1 + -6
true true
dist: [3980001, 0, -5, -6, -7, -4]
-5 > -1 + -7
true true
dist: [3980001, 0, -8, -6, -7, -4]
=====================
i: 4
-8 > 1 + 0
true false
-6 > -1 + -8
true true
dist: [3980001, 0, -8, -9, -7, -4]
-4 > 1 + -8
true true
dist: [3980001, 0, -8, -9, -7, -7]
-7 > -1 + -9
true true
dist: [3980001, 0, -8, -9, -10, -7]
-8 > -1 + -10
true true
dist: [3980001, 0, -11, -9, -10, -7]
=====================
i: 5
-11 > 1 + 0
true false
-9 > -1 + -11
true true
dist: [3980001, 0, -11, -12, -10, -7] // -> 여기서부터 cycle == ture
-10 > -1 + -12
true true
dist: [3980001, 0, -11, -12, -13, -7]
-11 > -1 + -13
true true
dist: [3980001, 0, -14, -12, -13, -7]

 

 

 

아래 문제는 3번 문제와 아주 흡사한 문제입니다.

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

​

https://devowen.com/250

위 링크는 원리를 설명해주는 링크입니다.