10014번 - Traveling Saga Problem 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 431 | 43 | 32 | 9.357% |
문제
n개의 정점으로 이루어진 가중치 없는 사과나무가 있고, 1번 정점에 사과 한 알이 매달려 있다.
여행을 좋아하는 사과는 사과나무의 모든 정점을 정확히 방문하려고 한다. 사과는 방문하지 않은 정점 중 현재 사과의 위치와 가장 거리가 큰 정점으로 움직이며, 그러한 정점이 여러 개일 경우 가장 번호가 큰 정점을 방문한다.
방문한 정점의 번호를 순서대로 적으면 길이 n의 순열을 얻을 수 있을 것이다. 사과가 n개의 정점을 방문한 순서를 출력하여라.
입력
첫 번째 줄에 사과나무의 정점의 수 n이 주어진다. (1 ≤ n ≤ 250000)
이후 n−1 개의 줄에 걸쳐 간선이 주어진다. 간선은 두 정수 s, e로 표현되며, s번 정점과 e번 정점을 잇는 간선이 존재함을 뜻한다. 간선의 가중치는 모두 1이다. (1 ≤ s, e ≤ n, s ≠ e).
당연하지만, 사과나무는 트리이다 (연결되어 있고 사이클이 없다).
출력
사과가 방문한 정점의 순서를 출력하라.
예제 입력 1
7 1 2 2 3 2 4 5 1 6 5 7 5
예제 출력 1
1 7 4 6 3 5 2
힌트
출처
Contest > Algorithmic Engagements > PA 2013 7-5번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호