| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 91 | 62 | 61 | 68.539% |
평화롭던 경곽 제국에 위협이 닥쳤다! 바로, 쌀나라의 승원이가 경곽 최고의 먹거리인 쌀을 먹기 위해 침공한 것이다.
이에 경곽 제국의 지배자인 시준이는 총 $K$개의 분열한 왕국들을 다시 합치려고 한다. 현재 $i$번째 왕국은 $1$부터 $N_i$까지 번호가 매겨진 $N_i$개의 마을과, 서로 다른 두 마을을 연결하는 $M_i$개의 다리로 이루어져 있다. 연결하는 마을이 같은 서로 다른 두 다리는 존재하지 않으며, 한 왕국 내의 모든 마을은 다리를 한 번 이상 이용해 서로 오갈 수 있다. 서로 다른 왕국의 마을 사이를 잇는 다리는 존재하지 않는다.
시준이는 각 왕국마다 하나의 마을을 도시로 선택한 후, 이 $K$개의 도시를 선형으로 잇는다. 즉, $K-1$개의 다리로 왕국마다 하나씩 선택된 $K$개의 도시를 모두 잇는데, 각 도시는 최대 $2$개의 다른 왕국의 도시와 연결되도록 한다. 이후 $K$개의 도시 중 한 곳을 수도로 정하려고 한다.
최종적으로, 시준이는 승원이를 막기 위해 수도로 군대를 모으려고 한다. 이를 효율적으로 하기 위해 수도에서 가장 먼 마을까지의 거리를 최소화해야 한다. 여기서 두 마을 사이의 거리는 한 마을에서 다른 마을로 이동할 때 거쳐야 하는 다리 개수의 최솟값으로 정의한다.
시준이를 대신해서 $K$개의 왕국의 도시를 선택하고, $K$개의 도시를 선형으로 이은 뒤, $K$개의 도시 중 수도를 선택하라. 그리고 선택한 수도에서 가장 먼 마을까지의 거리를 출력하라.
첫 번째 줄에 왕국의 수 $K$가 주어진다.
이후 $i = 1, 2, \cdots, K$에 대해 $i$번째 왕국의 정보가 다음과 같이 주어진다:
첫 줄에 마을의 수 $N_i$과 다리의 수 $M_i$이 주어진다.
다음 줄부터 $M_i$개의 줄 중 $j$번째 줄에 다리가 잇는 두 마을의 번호 $s_j, e_j$가 공백으로 구분되어 주어진다.
첫 번째 줄에 문제의 정답을 출력하라.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 30 | $K = 1$ |
| 2 | 15 | $N_i = 1 \ (1 \le i \le K)$ |
| 3 | 15 | $N_i \le 30 \ (1 \le i \le K)$ |
| 4 | 40 | 추가 제약 조건 없음 |
1 4 4 1 2 1 3 2 3 3 4
1
3 3 3 1 2 2 3 3 1 4 4 1 2 2 3 3 4 4 1 2 1 1 2
2
그림과 같이 설정했을 때, 수도로부터 제일 먼 마을까지의 거리는 $2$이다.
4 1 0 1 0 1 0 1 0
2
School > 경기과학고등학교 > IamCoder Qualification Test > 2026 IamCoder Qualification Test C번