3973번 - Time To Live 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 243 | 62 | 51 | 31.288% |
문제
대부분의 컴퓨터 네트워크는 트리 형태로 이루어져 있다. 즉, 각 컴퓨터와 다른 컴퓨터 사이의 경로는 항상 하나이다.
네트워크 패킷이 도착 장소까지 도착하지 못했을 때, 어떤 일정 시간이 지나면 그 패킷을 버린다. 이때, 이 시간을 Time to live(TTL)이라고 한다. TTL이 없다면, 패킷이 네트워크를 계속해서 순환하게 되고, 이는 라우팅 테이블의 에러를 일으킬 수 있기 때문이다.
라우터와 같은 네트워크 안의 다른 컴퓨터와 통신하는데 필요한 TTL의 최댓값이 가장 작게 라우터를 배치할 수 있다. 이렇게 네트워크와 다른 네트워크를 연결하는 라우터를 배치하면 최적의 방법으로 라우터를 배치할 수 있다.
위에서 설명한 네트워크가 주어졌을 때, 어떤 컴퓨터를 라우터로 사용해야 최대 TTL값이 가장 작아지는 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 c(1 ≤ c ≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 네트워크 안의 컴퓨터의 개수 N(1 < N ≤ 100,000)이 주어진다. 컴퓨터는 0번부터 N-1번까지 번호가 매겨져 있다. 다음 N-1줄에는 서로 연결되어 있는 컴퓨터의 번호 a와 b가 주어진다. (0 ≤ a,b < N) a와 b가 연결되어 있다면, b와 a도 연결되어 있는 것이다.
출력
이 네트워크에 라우터를 설치한다면, 어느 컴퓨터를 라우터로 사용해야 가장 큰 TTL 값이 작아지는지를 구한 뒤, TTL을 출력한다.
예제 입력 1
3 2 1 0 5 3 2 2 1 0 2 2 4 9 3 1 6 5 3 4 0 3 8 1 1 7 1 6 2 3
예제 출력 1
1 1 2
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2011 J번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호