31717번 - 현대모비스 자율 주행 테스팅 2 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 225 | 68 | 53 | 33.125% |
문제
이 문제는 현대모비스 자율 주행 테스팅 1 문제와 입력 형식이 다릅니다. 이 문제의 코드로 현대모비스 자율 주행 테스팅 1 문제를 해결할 수 없음에 유의하세요.
현대모비스는 모빌리티 플랫폼 프로바이더로서 SDV(Software Defined Vehicle)의 시대를 선도하고자 자율주행, 전동화, 커넥티비티 등 다양한 분야에서 SW 연구개발을 적극 진행하고 있다. 특히 현대모비스의 서산 주행 시험장에서는 자율 주행 자동차 개발을 위한 시범 주행이 한창이다. 샘플 주행 트랙은 모두 $M$종류이며, 각 샘플 주행 트랙에는 $1$번부터 $M$번까지의 번호가 매겨져 있다. $i$번 샘플 주행 트랙은 $2$행 $N_i$열로 이루어져 있으며, 트랙의 각 칸은 도로 혹은 장애물 중 하나로 구성되어 있다. 시범 주행 트랙은 $K$개의 샘플 주행 트랙을 차례로 이어 붙여 만든 형태이다. 시범 주행 트랙에 쓰인 샘플 주행 트랙의 번호를 차례로 $A_1,A_2,\cdots ,A_K$라 하면 시범 주행 트랙은 $2$행 $\sum_{i=1}^KN_{A_i}$열의 형태가 된다. 자동차는 아래의 두 가지 방법을 이용하여 트랙 위를 이동할 수 있다.
- 차선 변경: 자동차가 같은 열의 다른 행으로 이동한다. 즉 자동차의 현재 위치가 $1$행 $j$열이라면 $2$행 $j$열로, $2$행 $j$열이라면 $1$행 $j$열로 이동한다.
- 직진: 자동차가 같은 행의 다음 열로 이동한다. 즉 자동차의 현재 위치가 $i$행 $j$열이라면 $i$행 $j+1$열로 이동한다.
두 경우 모두 도착하는 칸에 장애물이 있어서는 안 된다.
시범 주행은 시범 주행 트랙의 첫 번째 열에서 시작하며, 마지막 열에 도달하면 끝난다. 시작하는 칸이나 끝나는 칸은 자유롭게 정할 수 있다. 단, 시작하는 칸과 끝나는 칸은 모두 도로여야 한다. 자율 주행 자동차가 시범 주행 트랙을 완주할 수 있는지 판별하고, 완주하는 것이 가능하다면 완주하기 위해 필요한 최소 이동 횟수를 구하여라.
입력
첫째 줄에 샘플 주행 트랙의 종류 수 $M$, 샘플 주행 트랙을 이어 붙인 횟수 $K$가 공백으로 구분되어 주어진다. $(1 \le M, K \le 200\ 000)$
둘째 줄에 시범 주행 트랙을 구성하는 샘플 주행 트랙의 번호 $A_1, A_2, \cdots, A_K$가 공백으로 구분되어 차례대로 주어진다. $(1 \le A_i \le M)$
셋째 줄부터 $2M$개의 줄에 걸쳐 $i$번 샘플 주행 트랙의 정보가 주어진다.
$2i+1$번째 줄에 $i$번 샘플 주행 트랙의 $1$행을 나타내는 길이가 $N_i$인 문자열 $S_{i1}$이 주어진다. $(1 \le N_i \le 500\ 000)$
$2i+2$번째 줄에 $i$번 샘플 주행 트랙의 $2$행을 나타내는 길이가 $N_i$인 문자열 $S_{i2}$가 주어진다.
모든 문자열은 . 또는 #으로 구성됨이 보장된다. .은 도로, #은 장애물을 의미한다. $N_i$의 합이 $500\ 000$ 이하임이 보장된다.
출력
자율 주행 자동차가 시범 주행 트랙을 완주하기 위해 필요한 최소 이동 횟수를 출력하여라. 트랙을 완주하는 것이 불가능하면 대신 -1을 출력하여라.
예제 입력 1
2 3 1 2 1 #.. ... .. #.
예제 출력 1
9
예제 입력 2
3 3 1 3 1 .#. ... ## ## . #
예제 출력 2
8
예제 입력 3
2 2 1 2 ... ... #.. ..#
예제 출력 3
6
예제 입력 4
2 3 1 2 1 ..# ... . #
예제 출력 4
-1
출처
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Senior Division D번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Open Contest F2번
- 문제를 만든 사람: leo020630
- 문제를 검수한 사람: 99asdfg, hyperbolic, lky7674, mjhmjh1104, nick832, queued_q, slah007, tony9402, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호