[백준 14675] 단절점과 단절선

1. 문제

https://www.acmicpc.net/problem/14675

14675번: 단절점과 단절선

2. 접근 방법

단절점과 단절선이라는 용어가 나와서 쫄았었는데, 별 거 아니었습니다.

 

문제에 나온대로 적어보자면,

• 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다.
• 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절선이라 한다.

그리고 주어지는 것은 트리입니다.

• 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프

처음에는 각 노드마다 dfs해서 찾아봐야하나 ? 했는데,

트리를 그려보고 앗차차 싶었습니다.

 

일단 모든 간선은 단절선입니다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋ ㅜㅜ

왜냐면 트리 내에서 간선은 모두 어떤 노드 2개를 연결하고 있기 때문에, 간선을 지우게 되면 트리가 2개로 나뉘게 되지요 

그리고 해당 노드와 연결된 노드가 두 개 이상이라면 해당 노드는 단절점이 됩니다.

3. 코드

python

import sys

input = sys.stdin.readline

N = int(input())
graph = {i: -1 for i in range(1, N+1)}
for _ in range(N-1):
    nums = list(map(int, input().split()))
    for num in nums:
        if graph[num] < 1:
            graph[num] += 1
q = int(input())
for _ in range(q):
    t, k = map(int, input().split())
    if t == 1:
        print('yes' if graph[k] == 1 else 'no')
    else:
        print('yes')

4. 마치며

처음에는 list로 해당 노드와 연결된 모든 노드를 넣었는데,

굳이 그럴 필요가 없게따 싶었습니다.

왜냐면 존재할 수 있는 상태의 종류가 총 3가지이기 때문이지요

(연결된 노드 없음, 연결된 노드 한 개 있음, 연결된 노드 두 개 이상)

 

그리고 참고로 input()으로 받으면 시간초과나서

sys.stdin.readline을 사용했습니다. 

 

느려

흥