9283번 - 보드 게임 "트리" 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 41 | 10 | 9 | 33.333% |
문제
원섭이와 상현이는 보드 게임을 구매했다. 게임판은 무한 이진 트리와 비슷한 형태이다. 게임판은 노드와 노드를 연결하는 양방향 도로로 이루어져 있다.
루트 노드는 게임판의 가장 위에 있고, 이 노드의 레벨은 0이다. 모든 노드는 항상 두 자식을 가지며, 왼쪽 자식과 오른쪽 자식이다. 왼쪽 자식의 위치는 부모 노드의 왼쪽 아래이고, 오른쪽 자식의 위치는 오른쪽 아래이다. 자식 노드의 레벨은 부모 노드의 레벨보다 1 크다.
도로는 부모 노드와 자식 노드를 연결하는 도로가 있고, 같은 레벨에 있는 노드를 모두 연결하는 도로가 있다. 같은 레벨에 있는 노드를 모두 연결하는 도로는 각 레벨의 가장 왼쪽 노드에서 시작하며, 각각의 노드와 그 오른쪽에 있는 노드를 연결한다.
한 노드에서 도로를 한 번 이용해서 다른 노드로 이동할 수 있다. 이동은 다음과 같이 총 5가지가 있으며, 한 글자로 나타낼 수 있다.
- 왼쪽 자식으로 이동: 1
- 오른쪽 자식으로 이동: 2
- 부모 노드로 이동: U
- 같은 레벨의 바로 왼쪽에 있는 노드로 이동: L
- 같은 레벨의 바로 오른쪽에 있는 노드로 이동: R
위와 같은 이동의 연속을 경로라고 한다.
예를 들어, 루트 노드에서 '221LU'로 이동한다면, A가 적힌 노드로 이동할 수 있다.
게임판 위의 두 노드가 주어진다. 이때, 한 노드에서 다른 노드로 이동하는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작상하시오. 두 노드는 루트에서 이동한 경로로 주어지며, 두 경로가 같은 노드인 경우에 답은 0이다.
입력
첫째 줄에 루트에서 첫 번째 노드로 이동하는 경로가 주어진다.
둘째 줄에 루트에서 두 번째 노드로 이동하는 경로가 주어진다.
두 경로의 길이는 100,000을 넘지 않으며, 항상 올바른 경로이다. (즉, 이동할 수 없는 상황은 나타나지 않는다)
출력
첫째 줄에 한 노드에서 다른 노드로 이동하는데 필요한 이동 횟수의 최솟값을 출력한다.
예제 입력 1
221LU 12L2
예제 출력 1
3
힌트
문제의 그림은 예제를 나타낸다.
출처
Olympiad > Central European Olympiad in Informatics > CEOI 2013 > Day 2 4번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호