티스토리 뷰

ICPC/2014 인터넷예선

K. Traffic Jams

전명우 2014. 10. 8. 00:52

자동차가 C대 있고 각 자동차의 시작 위치가 다를 수 있다. 모든 자동차의 목적지는 1번 마을이고, 각 자동차는 최단 경로 중 임의의 한 경로로 이동한다고 하자. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없을 때, 목적지에 갈 수 있는 자동차의 최대 개수를 구하는 문제다.


이 문제는 2013년 월드 파이널 C번 문제와 지문 하나 다르지 않게 출제되었다. 다행히도 이 문제의 풀이를 미리 알고 푼 팀은 없는 것으로 알고 있다.


문제에서 제약 조건은 단 하나, 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없다는 것이다. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동하기 위한 필요충분조건은 두 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 같다는 조건이다. 따라서 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 서로 다르다면 독립적으로 볼 수 있다.


그렇다면 문제에서 중요한 것은 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 같은 자동차 집단이다. 이 집단에서 최대한 많은 자동차가 도착 마을로 갈 수 있어야한다. 이는 Ford-Fulkerson 알고리즘으로 구할 수 있다. Ford-Fulkerson 알고리즘을 위해 전체 그래프에서 유효한 간선을 정의해야한다. 유효한 간선이란, 임의의 마을에서 도착 마을로 가는 최단 경로에 포함되는 간선을 의미한다. 이 때 유효한 간선은 당연히 방향성을 갖는다. 이 방향성을 갖는 간선들로 이루어진 그래프에서 Ford-Fulkerson 알고리즘을 통해 최단 거리가 같은 자동차 집단에서 도착 마을로 가는 자동차의 최대 개수를 구할 수 있다.


'ICPC > 2014 인터넷예선' 카테고리의 다른 글

I. Stains  (0) 2014.11.11
J. Switch Array  (0) 2014.10.08
K. Traffic Jams  (0) 2014.10.08
G. Mutation  (0) 2014.10.08
E. Highway  (0) 2014.10.07
D. 헨리  (0) 2014.10.07
댓글
댓글쓰기 폼