목차
※ 쉽고 명확하게 풀이하실 수 있도록 문제 지문을 일부 수정했습니다. 실제 경진대회 문제 지문과 차이가 있는 점 참고 부탁드립니다.
언어별 메모리 제한/수행시간 제한(공통 적용)
- C/C++
메모리제한 512MB, 수행시간 2초
- Java
메모리제한 512MB, 수행시간 4초
- Python3
메모리제한 512MB, 수행시간 10초
Q1. 주행테스트
알고리즘
- 다익스트라
- 한붓그리기
- BFS
힌트
새롭게 생성된 구간 역시 통과해야 하는 구간입니다.
문제
현대모비스는 차량의 성능을 실험하기 위해 여러 테스트를 할 수 있는 주행 시험장을 갖추고 있다. 주행 시험장은 1번부터 N번까지 번호가 매겨진 N개의 차량 정비소와 M개의 주행 구간으로 구성되어 있다. 주행 구간은 정비소와 정비소를 양방향으로 이어주며, 시작과 끝이 같은 정비소일 수 있다.
주행 테스트 대상 차량은 1번 정비소에서 출발하여 모든 주행 구간을 한 번씩 통과한 뒤 1번 정비소로 돌아와야 하고, 1번 정비소에서 테스트의 통과 여부가 결정된다.
최근 성능을 시험할 차의 종류가 늘어나 기존의 주행 테스트 시설로는 모든 차종의 주행 테스트가 불가능하게 되었다. 이에 폐쇄되었던 시설을 활용하여 주행 테스트를 하고자 한다. 폐쇄되었던 주행시험장은 현재와 다른 테스트 방법 때문에 1번 정비소에서 출발하여 모든 주행 구간을 한 번씩 통과한 뒤 다시 1번 정비소로 돌아올 수 있는지 알 수 없는 상황이다. 만약 가능하다면 시설을 그대로 사용하고, 불가능하면 최소 개수의 주행 구간을 추가하여 시설을 사용하고자 한다.
주행 테스트 시설의 정보가 주어졌을 때, 조건을 만족하기 위해 추가해야 하는 최소 주행 구간의 개수를 구하시오.
