백준 - 두 로봇 - 15971 - swift

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

15971번: 두 로봇

 

bfs 또는 dfs , 그래프탐색 유형이다.
굉장히 좋은 문제라고 생각한다.
그래프탐색의 골드5의 난이도는 그렇게 어렵지 않지만, 핵심을 파악하는게 꽤 걸렸다. ( 사실 그마저도 다른 분의 코드를 참고해서 깨달았다. )

이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다.
N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다.

그래프에서 N개의 노드들이 서로 연결되어 있으면서, 간선의 수가 N-1개라면, 트리라는 것을 바로 캐치해야한다.
트리의 특징으로는, 두 노드 사이의 거리는 유일할 수 밖에 없다. 또 간선의 값들이 모두 양수이므로, 같은 노드를 두번 이상 지나지 않고 마지막 노드에 도착하는 경로가 최적의 경로일 수 밖에 없다.

두 로봇이 서로 통신을 하기 위해서는 동굴 내의 같은 통로 위에 위치해야만 한다. 참고로 임의의 통로의 양 끝에 위치한 두 방들도 그 통로 위에 위치해 있다고 간주한다.

즉 두 노드 사이의 경로는 유일하면서, 특정 간선위에서 만나야한다.
여기서 조금만! 생각하면 아주 쉽게 풀 수 있다. ( 이것을 캐치못했다 )
간단한 생각을 먼저 말하기 앞서 내가 먼저 푼 방식은,

내가 접근한 방식

경로는 유일하므로, 우선 유일한 경로를 찾는다. ( dfs로 찾아냈다. )
유일한 경로를 찾으면서, 해당 경로까지의 거리를 계산한다. - dp [ i ] = 첫번째 로봇의 위치로부터 i노드까지의 거리 합.
그래서 해당 유일한 경로안에서 탐색하면서 하나씩 텀을 주면서 두 노드사이의 거리를 최소화되는 지점을 찾았다.
예를 들어, 만약 두 로봇의 위치가, 3, 9 라면, 유일한 경로가 3, 4, 5, 6, 7, 8, 9 노드들이라면,
3부터 8까지 dp를 순회하면서 찾아낸다.
정말, 문제를 그대로 받아들여 푼 방식이다...

다른분의 좋은 접근법

하지만 다른 분의 코드를 보니, bfs로 푼 사람이 있었고,
나도 처음에는 bfs로 접근했지만, 100점중에 23점만 획득하지 못했다. 그 이유는 유일한 경로들을 모두 큐에 담아서, 메모리초과로 이어졌을 듯 싶다. 그래서 dfs로 풀었다.
도저히 bfs로 푸는 방법을 모르겠어서, 코드를 더 자세히 살펴봤고,
거기서 깨달았다.

경로는 유일하다. 즉, 두 로봇사이의 거리합은 이미 정해져있다.
그리고 같은 통로내의 위치해야한다는 뜻은, 유일한 경로상에 있는 특정의 간선을 하나 빼면 된다는 것...
즉 유일한 경로안에서 가장 최대값이 되는 간선을 하나 빼면 그만이다.

트리에, 유일한 경로까지는 캐치했지만, 그 이상을 캐치하지 못한 내 자신이 아쉽다

bfs - 최대값 간선 빼기 코드

let inp = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = inp[0], X = inp[1], Y = inp[2]
var nodes = Array(repeating: [(Int,Int)](), count: N+1)
for _ in 0..<N-1 {
    let l = readLine()!.split(separator: " ").map{Int(String($0))!}
    nodes[l[0]].append((l[1],l[2]))
    nodes[l[1]].append((l[0],l[2]))
}
var check = Array(repeating: false, count: N+1)
check[X] = true
var ans = X == Y ? 0 : Int.max
var queue: [(node: Int, dist: Int, maxDist: Int)] = [(X, 0, 0)]
var q = 0
while queue.count > q {
    let f = queue[q]
    q += 1
    if f.node == Y {
        print(f.dist - f.maxDist)
        break
    }
    for next in nodes[f.node] {
        if check[next.0] { continue }
        check[next.0] = true
        let nextMaxDist = max(f.maxDist, next.1)
        queue.append((next.0, f.dist+next.1, nextMaxDist))
    }
}

 

문제 그대로 받아들여 dfs로 푼 나의 첫번째 코드

let inp = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = inp[0], X = inp[1], Y = inp[2]
var nodes = Array(repeating: [(Int,Int)](), count: N+1)
for _ in 0..<N-1 {
    let l = readLine()!.split(separator: " ").map{Int(String($0))!}
    nodes[l[0]].append((l[1],l[2]))
    nodes[l[1]].append((l[0],l[2]))
}
var dp = Array(repeating: -1, count: N+1)
var ans = X == Y ? 0 : Int.max
var keeps = [X]

func dfs(start: Int, end: Int ) {
    if start == end {
        for i in 0..<keeps.count-1 {
            ans = min(ans, (dp[keeps.last!] - dp[keeps[i+1]]) + dp[keeps[i]])
        }
        return
    }
    for next in nodes[start] {
        if dp[next.0] != -1 { continue }
        dp[next.0] = dp[start]+next.1
        keeps.append(next.0)
        dfs(start: next.0, end: end)
        keeps.removeLast()
    }
}
dp[X] = 0
dfs(start: X, end: Y)

print(ans)