KTH Challenge 2014 G - Intercept

Intercept – Kattis, Kattis

문제를 다음과 같이 요약할 수 있다.

가중치가 있는 유향 그래프 G가 주어진다.

정점 s에서 정점 t로 가는 모든 최단 경로에서 반드시 지나는 정점 집합 V를 구하여라.

 

나의 잘못된 풀이는 다음과 같다.

정점 s에서 dijkstra를 돌려 정점 t로 가는 임의의 최단 경로 P를 구한다.

동시에 모든 정점으로의 최단 경로에 포함되는 간선 집합 E를 구한다.

E에 속하는 간선들만으로 무향 그래프 H를 구성하고 H에서의 모든 절단점을 구한다.

s와 t를 제외한 모든 정점 u에 대하여 u가 P에 속함과 동시에 H에서의 절단점이라면 u는 V에 속한다.

 

위의 풀이는 다음과 같은 반례가 존재한다.

5 5

0 1 100

1 2 100

2 3 100

2 4 100

0 4 300

0 3

 

s에서 t로 가는 최단 경로 상에 포함되지 않는 일부 정점이 H에서 사이클을 구성하면 답을 제대로 구하지 못한다.

물론 간선 집합 E를 잘 수정하여 이를 방지할 수 있고 결과적으로는 AC를 받을 수 있다.

하지만 정해가 보다 간결하기에 정해만 소개하려고 한다.

 

정해는 dijkstra와 bfs를 이용한다.

정점 s에서 dijkstra를 돌려 모든 정점으로의 최단 경로에 포함되는 간선 집합 E를 구한다.

E에 속하는 간선들만으로 역방향 그래프 H를 구성하고 정점 t에서 bfs를 돌린다.

이때 queue에서 정점 u를 제거하였을 때 queue가 비게 된다면 u는 V에 속한다.

 

queue가 비었다는 것은 정점 u를 거치지 않고서는 다른 남아 있는 정점에 도달할 수 없다는 것을 의미한다.

solved.ac 기준 골드 수준일 듯 한데 아직 수련이 부족함을 느낀다.

 

2023/03/15 추가

위의 풀이는 정해와 상이하며 다음과 같은 반례가 존재한다.

5 5

0 1 100

1 2 300

1 3 100

3 4 100

4 2 100

0 2

 

업데이트된 나의 풀이를 소개한다.

주어진 그래프 G의 역방향 그래프 H를 구성하자.

G의 정점 s와 H의 정점 t에서 각각 dijkstra를 돌리면 s에서 t로 가는 최단 경로에 포함되는 간선 집합 E를 구할 수 있다.

E에 속하는 간선들만으로 새로운 그래프를 구성하고 다시 dijkstra를 돌리자.

정점 u를 pq에서 제거하였을 때 pq가 비게 된다면 s에서 t로 가는 최단 경로는 반드시 u를 포함하게 된다.

 

정해의 파이썬 코드에서 pq의 변수명으로 Q를 사용하였는데 나는 단순히 queue라고 생각하였다.

유사한 문제를 풀면서 코드를 복기해보니 나의 풀이는 말도 안 되는 풀이였고 금방 반례를 찾을 수 있었다.

데이터가 이렇게 약한 것도 신기하고 말도 안 되는 풀이에 수긍한 3개월 전의 나 자신도 신기하다.

 

끝