2022 현대모비스 알고리즘 경진대회 예선 문제

목차

  1. Dead or Arrive
  2. 주차 시스템
  3. ADAS 시스템
  4. 생산공정
  5. 도로망 설계

※ 쉽고 명확하게 풀이하실 수 있도록 문제 지문을 일부 수정했습니다. 실제 경진대회 문제 지문과 차이가 있는 점 참고 부탁드립니다.

언어별 메모리 제한/수행시간 제한(공통 적용)

  • C/C++

메모리제한 512MB, 수행시간 2초

  • Java

메모리제한 512MB, 수행시간 4초

  • Python3

메모리제한 512MB, 수행시간 10초


Q5. 도로망 설계

알고리즘

  • MCMF
  • 네트워크 플로우

문제


구름이가 살고 있는 도시는 N개의 지구와 각 지구를 잇는 M개의 양방향 도로로 이루어진 도로망을 가지고 있다.

이 도시에서는 재개발을 통해 오래된 도시 구조에서 오는 문제를 타파하고자 하고 있다. 구름이가 살고 있는 도시의 각 지구는 주택 지구 혹은 산업 지구로 나뉘는데, 이름 그대로 주택 지구에는 사람들이 살고 산업 지구에는 일터가 있어서 사람들은 보통 주택 지구에서 산업 지구로 출퇴근한다.

현대모비스에 입사한 구름이는 자율 주행 및 내비게이션 기능을 적절히 갱신하기 위해서, 도시에서 이뤄지는 재개발이 어떻게 진행될지를 알고 싶다. 구름이는 현재 도시의 재개발이 다음과 같은 과정을 통해 이루어질 예정인 것은 알고 있다.

  1. 1번 지구는 주택 지구, N번 지구는 산업 지구이다.
  2. 도시의 각 도로도 모두 재개발이 이루어질 예정인데, 주택 지구끼리 연결하는 도로일 때, 주택 지구와 산업 지구를 연결하는 도로일 때, 산업 지구끼리 연결하는 도로일 때 각각 재개발에 필요한 비용이 다르다. 이때, 주택 지구와 산업 지구를 오가는 통행량이 가장 많기 때문에 이 경우에 드는 재개발 비용이 가장 크다.
  3. 2번 지구부터 N-1번 지구까지 각각의 지구는 주택 지구 혹은 산업 지구 둘 중 하나가 될 수 있다. 이때 각 지구를 잇는 도로를 재개발하는데 드는 비용이 최소가 되도록 설정하려고 한다.
현대모비스알고리즘경진대회예선

예를 들어,  현재 도시가 위와 같은 도로망 구조를 가지고 있다고 가정해보자. 각 도로에 붙은 숫자는 맨 첫 번째부터 순서대로 (주택 지구끼리 연결할 때 비용, 주택 지구와 산업 지구를 연결할 때 비용, 산업 지구끼리 연결할 때 비용)에 해당한다.

이때,

1번 지구와 3번 지구를 주택 지구로, 2번 지구와 4번 지구를 산업 지구로 설정하는 경우, 각 도로를 재개발하는 데 드는 비용은 다음과 같다.

  • 1번 지구와 2번 지구를 잇는 도로: 주택 지구와 산업 지구를 연결하므로, 2의 비용이 필요
  • 1번 지구와 3번 지구를 잇는 도로: 주택 지구끼리 연결하므로, 2의 비용이 필요
  • 1번 지구와 4번 지구를 잇는 도로: 주택 지구와 산업 지구를 연결하므로, 7의 비용이 필요
  • 2번 지구와 4번 지구를 잇는 도로: 산업 지구끼리 연결하므로, 1의 비용이 필요

따라서, 총 2 + 2 + 7 + 1 = 12의 비용이 필요하고 이 경우가 최소이다.

구름이를 도와 위의 조건에 따라 재개발이 이루어질 때 필요한 최소 비용이 얼마인지 구하는 프로그램을 작성해보자.

Posted by
goorm

ANYONE CAN DEVELOP