목차
※ 쉽고 명확하게 풀이하실 수 있도록 문제 지문을 일부 수정했습니다. 실제 경진대회 문제 지문과 차이가 있는 점 참고 부탁드립니다.
언어별 메모리 제한/수행시간 제한(공통 적용)
- C/C++
메모리제한 512MB, 수행시간 2초
- Java
메모리제한 512MB, 수행시간 4초
- Python3
메모리제한 512MB, 수행시간 10초
Q5. 도로망 설계
알고리즘
- MCMF
- 네트워크 플로우
문제
구름이가 살고 있는 도시는 N개의 지구와 각 지구를 잇는 M개의 양방향 도로로 이루어진 도로망을 가지고 있다.
이 도시에서는 재개발을 통해 오래된 도시 구조에서 오는 문제를 타파하고자 하고 있다. 구름이가 살고 있는 도시의 각 지구는 주택 지구 혹은 산업 지구로 나뉘는데, 이름 그대로 주택 지구에는 사람들이 살고 산업 지구에는 일터가 있어서 사람들은 보통 주택 지구에서 산업 지구로 출퇴근한다.
현대모비스에 입사한 구름이는 자율 주행 및 내비게이션 기능을 적절히 갱신하기 위해서, 도시에서 이뤄지는 재개발이 어떻게 진행될지를 알고 싶다. 구름이는 현재 도시의 재개발이 다음과 같은 과정을 통해 이루어질 예정인 것은 알고 있다.
- 1번 지구는 주택 지구, N번 지구는 산업 지구이다.
- 도시의 각 도로도 모두 재개발이 이루어질 예정인데, 주택 지구끼리 연결하는 도로일 때, 주택 지구와 산업 지구를 연결하는 도로일 때, 산업 지구끼리 연결하는 도로일 때 각각 재개발에 필요한 비용이 다르다. 이때, 주택 지구와 산업 지구를 오가는 통행량이 가장 많기 때문에 이 경우에 드는 재개발 비용이 가장 크다.
- 2번 지구부터 N-1번 지구까지 각각의 지구는 주택 지구 혹은 산업 지구 둘 중 하나가 될 수 있다. 이때 각 지구를 잇는 도로를 재개발하는데 드는 비용이 최소가 되도록 설정하려고 한다.
예를 들어, 현재 도시가 위와 같은 도로망 구조를 가지고 있다고 가정해보자. 각 도로에 붙은 숫자는 맨 첫 번째부터 순서대로 (주택 지구끼리 연결할 때 비용, 주택 지구와 산업 지구를 연결할 때 비용, 산업 지구끼리 연결할 때 비용)에 해당한다.
이때,
1번 지구와 3번 지구를 주택 지구로, 2번 지구와 4번 지구를 산업 지구로 설정하는 경우, 각 도로를 재개발하는 데 드는 비용은 다음과 같다.
- 1번 지구와 2번 지구를 잇는 도로: 주택 지구와 산업 지구를 연결하므로, 2의 비용이 필요
- 1번 지구와 3번 지구를 잇는 도로: 주택 지구끼리 연결하므로, 2의 비용이 필요
- 1번 지구와 4번 지구를 잇는 도로: 주택 지구와 산업 지구를 연결하므로, 7의 비용이 필요
- 2번 지구와 4번 지구를 잇는 도로: 산업 지구끼리 연결하므로, 1의 비용이 필요
따라서, 총 2 + 2 + 7 + 1 = 12의 비용이 필요하고 이 경우가 최소이다.
구름이를 도와 위의 조건에 따라 재개발이 이루어질 때 필요한 최소 비용이 얼마인지 구하는 프로그램을 작성해보자.
