[백준 14675번] 단절점과 단절선 (python)

문제

그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다.

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

이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다.

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

트리의 정보와 질의가 주어질 때, 질의에 대한 답을 하시오. 

 

 

기록

(트리 3일차) 규칙 갖고 쉽게 풀 수 있는 문제였는데 괜히 정석대로 하려다가 시간초과 때문에 엄청 시간들였다,, 단절점은 맨 끝 노드만 아니면 모두 가능하고, 단절선은 모두 가능하다는 점이 키포인트였던 것 같다.

 

코드

<ver1>

from collections import defaultdict
import copy
import sys
sys.setrecursionlimit(10 ** 9)

def check_and_write_visited(tree, start, visited, n):
    if start in visited: return False
    visited.append(start)
    for node in tree[start]:
        if node != start :
            check_and_write_visited(tree, node, visited, n+1)
    return True


N = int(input())
edges = []
tree_ori = defaultdict(list)
for i in range(N-1):
    a, b = input().split()
    a, b = int(a), int(b)
    edges.append((a, b))
    tree_ori[a].append(b)
    tree_ori[b].append(a)

q = int(input())
for i in range(q):
    t, k = input().split()
    t, k = int(t), int(k)
    tree = copy.deepcopy(tree_ori)

    if t==1:
        for node in tree[k]:
            tree[node].remove(k)
        del tree[k]

    elif t==2:
        a, b = edges[k-1]
        tree[a].remove(b)
        tree[b].remove(a)

    visited = []
    count_graph = 0
    for node in list(tree.keys()):
        if node not in visited:
            count_graph+=1
            check = check_and_write_visited(tree, node, visited, 0)
            if check==False:
                print('no')
                break
    else:
        if len(tree)!=len(visited): print('no')
        elif count_graph < 2 : print('no')
        else : print('yes')

엄청 공들여서 작성한 첫번째 버전!!!! 겨우 작성하고 테스트케이스도 통과해서 좋았는데ㅜ 기록할겸 적어놔야겠다.

1. dictionary에 연결정보 양방향으로 저장해놓기

2. for문 돌 때마다 deepcopy로 위의 dict 복사해서 단절점 케이스일 때는 해당 노드와 엣지들 지우고 단절선 케이스일 때는 엣지 지우기

3. 필요없는 정보 지운 dict를 재귀적으로 탐색해서 cycle여부랑 노드 개수 확인하기

열심히 구현했지만 시간초과로 실패.....

 

<ver2>

from collections import defaultdict

N = int(input())
tree = defaultdict(list)
for i in range(N-1):
    a, b = input().split()
    a, b = int(a), int(b)
    tree[a].append(b)
    tree[b].append(a)

q = int(input())
for i in range(q):
    t, k = input().split()
    t, k = int(t), int(k)

    if t==1:
        if len(tree[k])<2:
            print('no')
            continue
    print('yes')

규칙 알고나서 그대로 적용했다. 위의 코드 다 날리고 단절점 케이스에서 끝 노드 지울 때만 'no' 출력하게 바꿨다.

그런데도 시간초과나서 이것저것 바꿔보다가 설마 입력때문인가 싶어서 입력 받는 부분만 변경했다.

 

<ver3>

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

q = int(stdin.readline())
for i in range(q):
    t, k = stdin.readline().split()
    t, k = int(t), int(k)

    if t==1:
        if len(tree[k])<2:
            print('no')
            continue

    print('yes')

성공한 코드! 앞으로 input() 말고 무조건 stdin.readline() 쓰자.............