24436번 - K번째 최단 경로 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 47 | 27 | 22 | 57.895% |
문제
Bob와 Alice는 그래프에서 최단 경로를 찾는 게임을 즐겨한다.
동생 Bob은 아직 어려서 실수를 많이 하기 때문에 Alice는 Bob가 연습할 수 있도록 다음과 같은 문제를 제시했다.
먼저, 길이를 나타내는 정수 $L$을 정한 후, $0$부터 $10^L-1$ 까지의 총 $10^L$개의 양의 정수를 이용하여 아래 규칙에 따라 그래프를 만든다:
- 노드: $0$부터 $10^L-1$ 까지의 각 정수는 그래프의 고유한 노드를 나타낸다. 이 때, 각 정수는 선행하는 $0$을 붙여 반드시 길이가 $L$이 되도록 만든다. 예를 들어 $L = 2$라면 $00, 01, 02, \dots, 98, 99$로 총 $100$개의 노드를 만들게 된다.
- 간선: 두 정점 $(x, y)$ 사이에 간선이 있으려면 $x$와 $y$의 $1$의 자리, $10$의 자리, ..., $10^{L-1}$의 자리를 비교했을 때 딱 한 곳만 달라야 하고 그 차이가 정확히 $1$이 되어야 한다. 예를 들어 $L = 2$인 경우, $00$과 $01$, $01$과 $11$, $27$과 $37$, $36$과 $46$ 사이에는 간선이 있고, $00$과 $02$, $01$과 $10$, $36$과 $47$ 혹은 $46$과 $57$사이에는 간선이 없다.
아래 그림은 $L = 2$ 인 경우 그래프의 일부를 보여준다.
위 규칙에 따라 그래프를 만든 뒤, Alice는 Bob에게 두 정점 $x$와 $y$사이의 최단 경로 중 사전 순으로 정렬했을 시 $K$번째에 해당하는 최단 경로를 찾아보라고 했다. 예를 들어 $L = 2$, $x = 37$, $y = 55$인 경우를 생각해보자. 이 경우 두 노드 사이의 최단 거리는 $4$이며, 아래와 같이 총 여섯 개의 최단 경로가 존재한다. 만약 $K = 3$이라면 정답은 $3$번째 최단 경로인 $37 - 36 - 46 - 56 - 55$가 된다.
- $37 - 36 - 35 - 45 - 55$
- $37 - 36 - 46 - 45 - 55$ 위의 경로와 비교하면 $3$번째 노드인 $35$가 $46$보다 사전 순으로 앞선다.
- $37 - 36 - 46 - 56 - 55$ 위의 경로와 비교하면 $4$번째 노드인 $45$가 $56$보다 사전 순으로 앞선다.
- $37 - 47 - 46 - 45 - 55$ 위의 경로와 비교하면 $2$번째 노드인 $36$이 $47$보다 사전 순으로 앞선다.
- $37 - 47 - 46 - 56 - 55$ 위의 경로와 비교하면 $4$번째 노드인 $45$가 $56$보다 사전 순으로 앞선다.
- $37 - 47 - 57 - 56 - 55$ 위의 경로와 비교하면 $3$번째 노드인 $46$이 $57$보다 사전순으로 앞선다.
입력으로 $L$, $K$, $x$, $y$가 주어졌을 때 Bob을 도와 $x$와 $y$사이의 최단 경로 중 사전 순으로 $K$번째 최단 경로를 구해보자. 만약 $x$와 $y$사이의 최단 경로의 개수가 $K$보다 작다면 "NO"를 출력하도록 한다.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 입력은 한 줄에 $L$, $K$, $x$, $y$가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
$K$번째 최단 경로가 존재하는 경우 해당 최단 경로를 출력하고, 그렇지 않은 경우 "NO"를 출력한다 (따옴표 제외).
제한
- $1 ≤ T ≤ 15$
- $2 ≤ L ≤ 4$
- $1 ≤ K ≤ 10^{18}$
- $0 ≤ x, y < 10^L$
- $x$, $y$는 언제나 선행 $0$을 포함하여 길이가 $L$인 형태로 주어진다.
예제 입력 1
7 2 1 20 22 2 2 20 22 3 3 008 258 3 22 008 258 4 10 2022 3141 4 61 2022 3141 4 1000000000000000000 0000 9999
예제 출력 1
20 21 22 NO 008 018 028 038 048 148 248 258 NO 2022 2021 3021 3031 3041 3141 NO 0000 0001 0002 1002 1012 1022 1122 1123 1133 1143 1243 2243 3243 3244 4244 4254 4354 4364 5364 6364 6464 6474 6484 6584 6684 7684 7784 7785 7786 7787 7788 7888 7988 8988 8998 9998 9999
- 예제 1-2: $20$과 $22$사이의 최단 경로는 $20 - 21 - 22$ 하나 뿐이다.
- 예제 3-4: $008$과 $258$사이의 최단 경로는 총 $21$개 존재한다.
- 예제 5-6: $2022$와 $3141$사이의 최단 경로는 총 $60$개 존재한다.
예제 입력 2
7 2 1 37 55 2 2 37 55 2 3 37 55 2 4 37 55 2 5 37 55 2 6 37 55 2 7 37 55
예제 출력 2
37 36 35 45 55 37 36 46 45 55 37 36 46 56 55 37 47 46 45 55 37 47 46 56 55 37 47 57 56 55 NO
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호