[알고리즘] 단절선(브릿지) [백준 11400번 - 단절선]

2023년 5월 13일

문제 링크 : 11400번 - 단절선

문제

 

그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.

단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.

입력

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다.

그래프의 정점은 1부터 V까지 자연수이다.

출력

첫째 줄에 단절선의 개수 K를 출력한다.

둘째 줄부터 K개 줄에는 단절선을 사전순으로 한 줄에 하나씩 출력한다. 간선은 "A B" 형식으로 출력해야 하고, A < B를 만족해야 한다. 같은 간선은 한 번만 출력하면 된다. 즉, "A B"를 출력한 경우에 "B A"는 출력할 필요가 없다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 단절점과 단절선

---

문제 접근

단절선이란, 노드 사이를 잇는 어느 간선을 제거했을 때, 그래프가 2개로 나눠지는 간선을 의미한다. 같은 의미로 브릿지라고도 표현한다.

위와 같은 그래프가 있을 때, 이 그래프의 단절선은 어떻게 찾을 수 있을까?

1번 노드를 시작으로, 깊이우선탐색을 진행해보자. 1 -> 2, 2 -> 3을 거쳐 3번 노드는 1번 노드와 연결되어 있으므로, 결론적으로 노드 1,2,3은 중간에 간선이 하나 끊어져도 다른 우회로를 통해 서로 이동할 수 있기에 단절선 아니게 된다. 허나 1 -> 4 경로는 우회로가 없기에 1 - 4는 단절선이 된다

그렇다면, 특정 간선이 단절선인지 어떻게 판단할 수 있을까? 이를 판단하기 위해 주변 최소 순번이라는 개념을 도입하였다.

주변 최소 순번이란, 위의 그래프를 예시로 빌어, 1번 노드부터 DFS를 진행하였을 때, 깊이 우선 탐색을 진행할 때마다 순서가 1씩 증가한다고 가정한다면

• 1번 노드는 순번이 1
• 2번 노드는 순번이 2
• 3번 노드는 순번이 3

일 것이다. 여기서 3번 노드는 1번 노드를 탐색하게 되는데, 처음 탐색 노드로 다시 되돌아 왔으므로 이는 1 -> 2 -> 3 -> 1의 길이 존재 하면서도 1 -> 3 -> 2 -> 1 의 길도 존재함을 알 수 있다. 서로 노드가 우회로를 가지고 있다면, 해당 경로에 존재하는 노드들이 경로상에 존재하는 주변의 순번들 중 가장 최솟값으로 대체시키는 것이다. = 주변 최소 순번으로 대체된다.

1번 노드의 순번이 가장 작은 1을 가지니, 2번 노드와 3번 노드는 주변 최소 순번인 1을 가지게 된다.

그렇다면 다음 노드인 4번 노드를 탐색해보자.

• 4번 노드는 순번이 4

하지만 4번 노드는 1번 노드로 가는 경로에 대해 우회로가 없기 때문에, 4번 노드의 주변 최소 순번은 4이다.

여기서 알 수 있는 단절선 판단 방법은, 자식노드 즉, 서브트리의 주변 최소 순번이 부모노드의 주변 최소 순번보다 크다면, 사이를 잇는 간선은 단절선이 되는 것이다.

 

 

---

순서도

1. 그래프를 연결리스트 형태로 입력 받음

2. DFS를 이용해그래프의 모든 노드를 탐색
	2-1. 탐색 과정에서 우회로 즉, 사이클이 존재한다면 사이클을 구성하는 노드들 중
    	가장 작은 순번 값(주변 최소 순번)을 사이클을 구성하는 노드가 모두 부여받음.
    	2-2. 부모노드 - 자식노드 각각의 주변 최소 순번 값을 비교하며,
    	자식 노드의 주변 최소 순번 값이 부모 노드보다 크다면, 사이를 잇는 간선은 단절선임
        
3. 단절선을 출력하는데, "출력 조건"에 주의하여 출력 포맷을 설정하여 단절선을 출력한다.

 

 

---

입력 예제

7 8
1 4
4 5
5 1
1 6
6 7
2 7
7 3
2 3

위 입력 예제를 그래프로 그려보자.

<1번 노드부터 DFS를 진행할 것>

탐색하며 각 노드에 순번을 부여할 것이고, 문제 접근에서 언급한 것처럼 사이클이 생기면 해당 사이클을 구성하는 노드들 중, 가장 적은 순번인 주변 최소 순번을 모든 구성 노드들의 순번으로 통일시킬 것이다.

 

<탐색했던 노드로 되돌아왔다>

이전에 방문한 적 있는 노드로 되돌아왔다라는 것은, 사이클이 존재한다는 의미이다. 사이클이 존재하면 해당 사이클을 구성하는 노드들 중 가장 작은 순번인 주변 최소 순번으로 모든 노드의 순번을 통일시켜야 한다.

위 1 - 4 - 5 사이클에서 주변 최소 순번은 1이기 때문에 4번 노드와 5번 노드도 1로 순번을 1로 바꾸어 준다.

<주변 최소 순번으로 통일>

이어서 탐색을 진행해보자.

<탐색했던 노드로 되돌아왔다>

사이클이 생겼다. 해당 사이클을 구성하는 노드들의 순번을 주변 최소 순번으로 통일시켜주자. 7 - 2 - 3 사이클에서의 주변 최소 순번은 5이다.

<주변 최소 순번으로 통일>

모든 노드를 방문하여 탐색했다. 위 그래프의 정보로 어떤 간선이 단절선인지 알 수 있겠는가?

부모노드와 자식노드의 최종 순번이 다르다면 그 사이를 잇는 간선은 단절선이다.

(부모 -> 자식 순으로 항상 탐색하기에, 부모노드의 최종 순번이 자식노드의 최종 순번보다 작다는 조건이 좀 더 정확한 표현이다.)

위 그래프에서 단절선을 표현하면 다음과 같다.

<1 - 6 , 6 - 7 사이 간선은 단절선>

 

정말 단절선이 맞는지까지 확인까지 해보자.

 

<1 - 6 간선 제거>

1 - 6 간선을 제거하니 그래프가 둘로 나뉘었음이 확인되었다.

 

<6 - 7 간선 제거>

6 - 7 간선을 제거하니 그래프가 둘로 나뉘었음이 확인되었다.

출력 예제

2
1 6
6 7

---

주의할 점

1. 해당 문제는 출력 조건이 다음과 같다. 나는 이 출력 조건에 맞추려는 데에 시간을 상당히 쓴 유형이다...

• 단절선을 "A B" 형태로 출력함에 있어, 무조건 A가 B보다 작은 포맷을 지켜야 한다.
• 단절선이 K개면, K줄에 걸쳐 단절선들을 "A B" 형태로 출력해야 하는데, A 기준 사전순으로 출력해야 한다. 단절선 "6 7" , "1 6"이 존재할 때는 A 기준 사전 순으로 출력해야 하니 "1 6"을 먼저 출력하고,"6 7"을 나중에 출력해야 한다.
• 6 - 7 간선과 7 - 6 간선은 같은 간선이니 중복 출력하지 말아야 하는 점에 유의해야 한다.

 

---

전체 코드

#11400

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(start, parent):
    global cnt
    cnt += 1
    visited[start] = True # 방문한 노드는 True로 분류
    order[start] = cnt # 방문 순서 기입
    lsv = order[start] # 주변 최소 순번 변수 lsv

    for childNode in graph[start] : # 해당 노드와 연결된 자식노드들 탐색
        if childNode == parent : # 부모노드로 돌아가는 것은 무시한다
            continue
        
        if visited[childNode] == True : # 이미 방문한 상태라면
            lsv = min(lsv, order[childNode]) # 방문했던 노드를 주변 최소 순번으로 설정하고 진행
            continue
        
        subtree = dfs(childNode, start) # 서브트리도 dfs 탐색
        lsv = min(subtree, lsv) # 주변 최소 순번이 서브트리의 부모 노드와 주변 최소 순번 노드 중, 작은 값으로 설정

        # 현재 간선을 제외하고 우회로가 없다면 : 브릿지
        """판별 방법"""
        # 서브트리의 dfs 반환 값(주변 최소 순번)이 부모 노드의 순번보다 크다 : 브릿지
        if subtree > order[start] :
            bridge.add(tuple(sorted([start,childNode])))
    
    return lsv # 주변 최소 순번을 return


if __name__ == "__main__":
    V,E = map(int, input().split())

    graph = [[]for _ in range(0,V+1)] # 그래프 틀 선언
    # 크기가 노드의 개수 + 1인 이유 : 0번째 인덱스는 더미로 둘 것이기 때문.

    visited = [False] * (V+1) # dfs를 위한 방문여부 확인 bool 리스트
    # 크기가 노드의 개수 + 1인 이유 : 0번째 인덱스는 더미로 둘 것이기 때문.

    order = [-1] * (V+1) # 순회를 체크하기 위한 배열 선언. -1로 초기화
    # 크기가 노드의 개수 + 1인 이유 : 0번째 인덱스는 더미로 둘 것이기 때문.


    for i in range(0,E):
        v1, v2 = map(int,input().split())
        # 그래프에 각 노드의 연결성 삽입
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    #graph를 출력하면 인접리스트의 형태로 저장되었음을 알 수 있다.
    
    bridge = set() # 브릿지를 담을 중복제거 배열 선언

    cnt = 0 # 노드 방문 순서를 나타내는 변수
    
    dfs(1, None)
    
    # 모든 간선의 양 끝점은 [작은수 노드, 큰 수 노드] 로 통일시키기 위해 정렬을 진행
    # 이는 간선의 양 끝점을 입력받아 브릿지 여부 판단할 때, 데이터의 정렬을 통일시켜 브릿지인지 판단하기 용이하기 위함.
    
    bridge = sorted(bridge, key=lambda x : (x[0], x[1]))
    print(len(bridge))
    for x,y in bridge:
        print(x,y)

 

---

풀이 후기

작년 알고리즘 수업 때, 과제로 받았던 팀프로젝트 중 내가 맡았던 부분이 브릿지 찾기 문제였다. 처음 이 알고리즘을 접했을 땐 이해가 잘 안돼서 나름 이해하겠다고 여러 블로그 포스팅 글을 참고하며 내 것으로 만들고자 상당히 노력했던 기억이 새록새록하다. 이 포스팅을 통해 또 누군가가 비슷한 경위로 도움을 받게 되는 날이 오면 좋겠다.