[BOJ_14675] 단절점과 단절선

14675번: 단절점과 단절선

 

✅ 문제 설명

트리에서 단절점(cut vertex)과 단절선(bridge)을 구하는 문제입니다.

---

단절점, 단절선?

단절점: 하나의 컴포넌트(connected componenet)로 이루어진 그래프에서 한 정점을 제거했을 때, 컴포넌트의 개수가 증가하는 정점을 단절점이라고 한다.

단절선: 하나의 컴포넌트(connected componenet)로 이루어진 그래프에서 한 간선을 제거했을 때, 컴포넌트의 개수가 증가하는 간선을 단절선이라고 한다.

 

✅ 접근 방식

단절점을 Naive하게 찾는 방법은 모든 정점을 하나씩 선택하여(V) 제거해 본 후, 그래프가 나눠지는 파악해보는 방법이 있습니다(V+E). 이 방법의 시간 복잡도는 O(V*(V+E))가 됩니다.

 

다음의 단절점, 단절선 조건을 이용하면 단 한번의 DFS 탐색으로 모든 단절점과 단절선을 구해볼 수 있습니다.

---

단절점 조건

• 우회로가 존재하면 안됩니다. (즉, 현재 정점 V 이후에 방문한 Vafter가 V를 거치지 않고, V 이전에 방문했던 정점 Vbefore에 갈 수 있다면 단절점이 아닙니다.)
• 연결된 간선이 2개 이상이어야합니다. (그래야 단절점을 없앴을 때 2개 또는 그 이상으로 나눠지기 때문입니다. )

---

단절선 조건

• 우회로가 존재하면 안됩니다. (즉, 간선 E가 있을 때, 간선 반대쪽에 있는 노드에서 다른 반대쪽으로 갈 수 있는 길이 간선 E 말고도 있다면 단절선이 아닙니다.)

 

---

근데 우리의 문제는 그냥 그래프에서의 단절점, 단절선을 찾는 것이 아닌 트리에서의 단절점, 단절선을 찾는 것입니다.

 

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

트리에서의 단절점, 단절선은 다음과 같습니다.

• 트리는 사이클이 없기 때문에 임의의 노드에서 다른 노드로 가는 경로(path)는 단 1개만 존재합니다.
  (즉, 우회로가 존재하지 않습니다.)
• 따라서 해당 노드에 연결된 간선만 2개 이상이면 단절점입니다.
• 따라서 모든 선이 단절선입니다.

 

✅ 코드 설명

import sys

N = int(sys.stdin.readline())
tree = [[] for i in range(N)]

for i in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a - 1].append(b)
    tree[b - 1].append(a)

노드 N개짜리 트리이기 때문에 N개의 배열을 가진 인접리스트를 만들어 주었습니다. 이후 N-1개 줄에 걸쳐 입력되는 간선의 정보 a,b를 받아 (이는 a정점과 b정점이 연결되어있다는 뜻)  인접리스트를 만들어 트리를 구성해줍니다.

 

q = int(sys.stdin.readline())
for i in range(q):
    t, k = map(int, sys.stdin.readline().split())
    if t == 1:  # 노드k가 단절점인지?
        if len(tree[k - 1]) >= 2:
            print("yes")
        else:
            print("no")
    else:  # k번째의 입력의 간선이 단절선인지?
        print("yes")

q개의 질의를 받습니다. t가 1일때는 k번 정점(노드k)가 단절점인지에 대한 질의이고, t가 2일때는 입력에서 주어지는 k번째 간선이 단절선인지에 대한 질의입니다. 앞에서 말했던 트리에서 단절점, 단절선 조건에 따라 코드를 짜주었습니다.

 

✅ 최종 코드

# 단절점과 단절선

import sys

N = int(sys.stdin.readline())
tree = [[] for i in range(N)]

for i in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a - 1].append(b)
    tree[b - 1].append(a)

q = int(sys.stdin.readline())
for i in range(q):
    t, k = map(int, sys.stdin.readline().split())
    if t == 1:  # 노드k가 단절점인지?
        if len(tree[k - 1]) >= 2:
            print("yes")
        else:
            print("no")
    else:  # k번째의 입력의 간선이 단절선인지?
        print("yes")

 

❇️ 코멘트

• 트리는 사이클이 없기 때문에 임의의 노드에서 다른 노드로 가는 경로(path)는 단 1개만 존재한다는 트리의 특성을 다시 기억해볼 수 있는 좋은 문제였습니다.
• 그래프와 트리에서의 단절점과 단절선의 조건에 대해 정리해 볼 수 있었습니다.
• 그래프에서 단절점, 단절선을 찾으려면 우회로가 있는 지 체크해봐야하는데 어떻게 체크해야할지 아직 모르겠어서 그래프에서의 단절점, 단절선 찾기 문제도 풀어봐야겠습니다.