목차
※ 쉽고 명확하게 풀이하실 수 있도록 문제 지문을 일부 수정했습니다. 실제 경진대회 문제 지문과 차이가 있는 점 참고 부탁드립니다.
언어별 메모리 제한/수행시간 제한(공통 적용)
- C/C++
메모리제한 512MB, 수행시간 2초
- Java
메모리제한 512MB, 수행시간 4초
- Python3
메모리제한 512MB, 수행시간 10초
Q3. ADAS 시스템
알고리즘
- 우선순위 큐
- 구현
힌트
모든 좌표는 도착 직전까지 후보에 올라갑니다.
문제
현대모비스는 운전자가 안전하고 편리하게 주행하도록 도와주는 ADAS 시스템을 개발했다. ADAS 시스템의 담당 개발자인 구름이는 ADAS 시스템을 보완하기 위해서 가상 테스트 주행을 진행하여, ADAS 시스템이 이동한 경로의 위험 점수를 측정하고자 한다.
가상 주행 환경은 2차원 좌표 평면으로 표현할 수 있다. 좌표 평면은 위아래로 W줄, 좌우로 H줄의 격자로 구성되어 있으며, 맨 왼쪽 위 좌표는 (0, 0), 맨 오른쪽 아래 좌표는 (W-1, H-1)이다.
이때 임의의 정수 0 ≤ a < W, 0 ≤ b < H에 대해 (a, b) 좌표의 점은 일반 점 혹은 P- 점, 혹은 점 S, 점 E 중 하나로 표현된다.
가상 주행 시스템은 점 S에서 시작해서 점 E로 이동하며, 점 E에 도착하는 순간 주행이 종료된다. 주행 과정에서 ADAS 시스템은 다음 조건에 따라 이동한다.
- 주행 과정에서 어떤 점 (a, b)에 방문하면 ADAS 시스템은 (a-1, b), (a, b-1), (a+1, b), (a, b+1)의 해당 점 주변 4방향 중, 아직 방문한 적 없는 점들을 이동 후보 정점 목록에 추가한다. 좌표 평면 바깥에 해당하는 점인 경우는 후보에서 제외한다.
- ADAS 시스템은 이동 후보 정점 목록 중에서 방문할 다음 점을 아래의 우선순위에 따라 결정한다.
- 점 E가 가장 우선순위가 높으며, 다음은 P- 점, 그다음은 일반점이다. 우선순위가 가장 높은 점을 먼저 방문한다.
- 우선순위가 같은 점이 여러 개 있다면, 점의 좌표를 (a, b)로 표현했을 때, a 값이 작은 것이 우선, a 값이 같다면 b 값이 작은 것을 우선적으로 방문한다.
가상 주행 과정에서 위험 점수는 처음에 0점에서 시작하며, 각 점을 방문할 때 다음 규칙에 따라 위험 점수가 증가한다.
- 점 S와 점 E는 방문할 때 위험 점수가 증가하지 않는다.
- 일반 점의 경우, 해당 점을 중심으로 주변 3*3 크기 안에서 자신을 제외한 p- 점의 개수만큼 위험 점수가 증가한다. 따라서, 아래 그림의 일반 점은 위험 점수가 2점이 된다.
- P- 점의 경우, (일반 점과 동일한 방식으로 계산한 위험 점수 – 3)만큼 위험 점수가 증가한다. 이 값이 음수인 경우 위험 점수가 그만큼 감소한다.
모든 주행을 마친 후, 위험 점수가 0보다 작다면 위험 점수는 0으로 측정한다.
ADAS 시스템이 목적지에 도착하면 가상 주행을 종료한다. 이때 ADAS 시스템이 측정한 위험 점수를 출력해보자.
예시
현재 ADAS 시스템의 정보 수집으로 얻은 도로의 좌표 평면이 아래와 같다고 하자.
점 S가 좌표 (0, 3)에 있으므로 주행은 (0, 3)에서 시작한다. 이때 위험 점수는 0점이다.
다음으로, 이동할 후보 정점에 (0, 2), (0, 4), (1, 3) 세 개의 정점이 추가된다. 그림에서 방문한 정점은 노란색, 후보 정점은 초록색으로 나타나 있다. 세 정점 모두 일반 정점이므로 우선순위는 동일하고, 여러 개인 경우 다음 정점을 선택하는 규칙에 따라 ADAS 시스템은 (0, 2) 정점에 방문하게 된다.
(0, 2) 정점은 규칙에 따라 위험 점수가 2점이므로, 위험 점수가 2만큼 상승한다. 다음으로, 이동할 후보 정점에 (0, 1), (1, 2) 두 개의 점이 추가된다. 총 5개의 후보 정점 중에서, 가장 우선순위가 높은 건 P- 점인 (0, 1)과 (1, 2)의 두 개 정점이다. 마찬가지로, 우선순위가 같은 정점이 여러 개인 경우 다음 정점을 선택하는 규칙에 따라 ADAS 시스템은 (0, 1)정점에 방문하게 된다.
(0, 1) 정점은 규칙에 따라 위험 점수가 1 – 3 = -2점이 되므로, 위험 점수가 2만큼 감소한다. 다음으로, 이동할 후보 정점에 (0, 0), (1, 1) 두 개의 점이 추가된다. 이 중에서 가장 우선순위가 높은 점은 점 E인 (1, 1)이므로, (1, 1)에 방문한다.
점 E에 방문했으므로, 주행을 종료한다. 이 가상주행의 위험 점수는 2 – 2 = 0이므로 0을 출력한다.
