[BOJ] 17352 여러분의 다리가 되어 드리겠습니다! (Python3)

문제

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, …, N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.

어제까지는 그랬다.

“왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다”며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다! 안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다. 일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라는 지시를 내렸다.

그런데 그 건축가가 당신이다! 안 그래도 천하제일 코딩대회에 참가하느라 바쁜데…

입력

첫 줄에 정수 N이 주어진다. (2 ≤ N ≤ 300,000)

그 다음 N - 2개의 줄에는 욱제가 무너뜨리지 않은 다리들이 잇는 두 섬의 번호가 주어진다.

출력

다리로 이을 두 섬의 번호를 출력한다. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력한다.

정답 코드

from collections import deque
n = int(input())
graph = [[] for i in range(n + 1)]

for i in range(n - 2):
    a, b = map(int, input().split())    
    graph[a].append(b)
    graph[b].append(a)
    
visited = [False for _ in range(n + 1)]
visited[0] = True
q = deque()

answer = 0
q.append(1)

while q:
    node = q.popleft()
    
    if not visited[node]:
        visited[node] = True
        
        answer = max(answer, node)
        
        for g in graph[node]:
            q.append(g)
            
print(answer, visited.index(False))
    

문제 풀이

처음에는 크루스칼 알고리즘으로 풀어야하나 했는데, 문제를 자세히 보니까 다리를 무조건 한개만 끊고, 경우의 수도 아무거나 출력해도 되어서 그냥 bfs로 풀었다.

무조건 1부터 시작해서 첫번째 그룹을 찾아내고, 탐색이 종료된 후 방문 하지 않은 인덱스를 같이 출력해서 풀었다.

솔직히 실버급 문제인것 같다.오랜만에 쉬운 문제…