백준 - 두 로봇 - 15971 - swift

백준 - 두 로봇 - 15971 - swift

https://www.acmicpc.net/problem/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.. 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..

from http://vapor3965.tistory.com/84 by ccl(A) rewrite - 2021-08-25 16:26:49