백준 - 오만식의 고민 (1219)

최종 풀이

struct Edge {
    let start: Int
    let end: Int
    let value: Int
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, start, end, M) = (input[0], input[1], input[2], input[3])
var edges = [Edge]()

// 에지 리스트 만들기
for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    edges.append(Edge(start: input[0], end: input[1], value: input[2]))
}

let money = readLine()!.split(separator: " ").map { Int(String($0))! }

// 벨만포드 알고리즘
var distance = Array(repeating: Int.min, count: N)
distance[start] = money[start]

for _ in 0..<N {
    for j in 0..<M {
        let now = edges[j]
        if distance[now.start] != Int.min && distance[now.end] < distance[now.start] + money[now.end] - now.value {
            distance[now.end] = distance[now.start] + money[now.end] - now.value
        }
    }
}

for _ in 0..<100 {
    for j in 0..<M {
        let now = edges[j]
        if distance[now.start] == Int.min {
            continue
        } else if distance[now.start] == Int.max || distance[now.end] < distance[now.start] + money[now.end] - now.value {
            distance[now.end] = Int.max
        }
    }
}

if distance[end] == Int.min {
    print("gg")
} else if distance[end] == Int.max {
    print("Gee")
} else {
    print(distance[end])
}

첫 번째 시도

이 문제에서 주의해야 할 점은 사이클이 있지만 이 사이클을 통해 도착 도시로 가지 못하는 경우가 있다는 것이다.

처음에는 기본적인 벨만포드 알고리즘을 사용할 때처럼 N번 순회한 후에 1번만 더 도착 도시의 값이 distance 값이 바뀌는지 확인하면 되지 않을까 생각했다.

let endDistance = distance[end]

for i in 0..<M {
    let now = edges[i]
    if distance[now.start] != Int.min && distance[now.end] < distance[now.start] + money[now.end] - now.value {
        distance[now.end] = distance[now.start] + money[now.end] - now.value
    }
}

if distance[end] == Int.min {
    print("gg")
} else if distance[end] != endDistance {
    print("Gee")
} else {
    print(distance[end])
}

그래서 이런 식으로 이전 distance 값과 현재 distance 값이 일치하는지 여부를 확인해서 Gee를 출력하고자 했다.

그러나 3%대에서 WA…

두 번째 시도

막연하게 사이클이 저~멀리 있어서 (..) 한 번만 더 알고리즘을 돌려도 distance 값이 업데이트 되지 않는 경우가 있겠구나 싶어서 N번 알고리즘을 실행한 후에 100번 (N의 최대값보다도 큰 값)을 더 알고리즘을 반복해서 양수 사이클이 충분히 전파될 수 있도록 하였다.

for _ in 0..<100 {
    for j in 0..<M {
        let now = edges[j]
        if distance[now.start] != Int.min && distance[now.end] < distance[now.start] + money[now.end] - now.value {
            distance[now.end] = distance[now.start] + money[now.end] - now.value
        }
    }
}

if distance[end] == Int.min {
    print("gg")
} else if distance[end] != endDistance {
    print("Gee")
} else {
    print(distance[end])
}

반복문만 추가하고 이전 distance 값과 비교하는 식의 로직은 그대로 가져갔더니 이번에는 16% 즈음에서 WA가 떴다.

세 번째 시도

대체 왜 틀렸을까 고민해보다가 반례를 발견했다.

3 0 2 4

0 1 9999

1 2 9999

1 1 9999

0 2 0

10000 10000 10000

Gee

내가 작성한 코드에서 위 예시를 실행해보면 20000 이 출력되었다.

그래프를 그려서 차근차근 확인해보면 1에서 사이클을 돌 때마다 distance 값이 1씩 업데이트된다. 그럼 약 10000번 정도를 반복해야 기존 2의 distance 값(20000)보다 커져서 distance 값을 업데이트 할 수 있다.

그런데 내 코드에서는 고작 100번만을 반복하니 사이클의 존재가 반영이 되지 않은 것이었다.

for _ in 0..<100 {
    for j in 0..<M {
        let now = edges[j]
        if distance[now.start] == Int.min {
            continue
				// 사이클에 포함되는 경우
        } else if distance[now.start] == Int.max || distance[now.end] < distance[now.start] + money[now.end] - now.value {
            distance[now.end] = Int.max
        }
    }
}

if distance[end] == Int.min {
    print("gg")
} else if distance[end] == Int.max {
    print("Gee")
} else {
    print(distance[end])
}

그래서 N번 반복한 후 추가적으로 100번 for문을 돌릴 때 현재 노드가 사이클에 포함되면 무조건 distance 값을 Int.max 로 설정해주었다.

이렇게 작성하면 도착 도시의 distance 값이 Int.min 이면 도착 도시로 가는 경로가 없는 경우, Int.max 이면 사이클에 포함되는 경우 (즉 돈을 무한히 가지고 있을 수 있는 경우), 둘 다 아니면 돈 액수의 최댓값을 출력할 수 있는 경우가 된다.

---

그래프 문제는 다양한 케이스들이 직관적으로 그려지지가 않아서 더욱 힘든 것 같다. 많이 연습하자..🥲