알고리즘 스터디를 하다가, 스터디원 한 분이 선정하신 문제를 풀다가 알게 된 유형이다.

처음에는 union-find 문제인 줄 알았으나, 알고보니 새로운 유형의 문제였다.!!

 

착각했던 만큼이나 알고리즘의 글로서의 개념은 매우 비슷하다.

union-find는 무향 그래프에서의 노드 간의 연결을, 동일한 부모 원소로 두면서 각 집합으로 표현을 한다.

SCC는 유향 그래프에서의 노드 간의 명확한 연결만을, 동일한 부모 원소로 두면서 각 컴포넌트(집합)으로 표현을 한다.

(그래서 강한 결합 알고리즘 알고리즘이라고 부른다.)

 

여기에서 "명확한 연결"이란 "두 노드 간의 자유로운 이동"을 뜻한다.

무향 그래프에서는 간선에 방향성이 없어 자연스럽게 자유로운 이동이 가능했지만,

유향 그래프에서는 간선에 방향성이 있어 a → b 는 가능해도 b → a 는 불가능 할 수도 있다.

 

그러나.. 개념적으로는 비슷하지만, 구현적으로는 전혀 다르다는 게 함정이다.. ㅎㅎ

그러면 SCC 알고리즘에 대해 조금 더 깊이 있게 알아보자.

 

 

1. 개념

 

사실 위의 글의 서문에서 Union-find와 SCC의 차이를 비교하며, 개념에 대한 언급을 했다.

이를 간략히 요약하면, 강한연결요소(SCC)는 "컴포넌트 내에서 노드들 간에 서로 자유롭게 이동 가능함"을 의미한다.

 

결론적으로 하나의 노드 또한 SCC가 될 수 있어, 유향 그래프의 모든 정점은 각각이 SCC가 되도록 분할이 가능하다.

참고로 무향 그래프는 전체가 하나의 SCC가 되므로 큰 의미가 없다.

 

 

2. 코드 이해

SCC 알고리즘의 개념과 동작 플로우를 확인하기 위해 여러 블로그 글을 읽었다.

처음에 글로서의 개념은 이해가 갔지만, 구현 코드를 보고 "왜 이렇게 작성된 거지?" 하면서 이해가 되지 않았던 부분이 있었다.

 

특히, 각 노드별 방문 순서에 따른 고유한 번호를 할당하고 있었는데 해당 부분에서 이해가 막혔다.

즉, 1)실제 노드 번호와 2)방문 순서에 따른 노드 번호 이렇게 관리한 셈이다.

그래서 알고리즘 코드를 먼저 작성하고, 테스트 코드들을 디버깅 하면서 이해하려고 했고 그 과정을 적으려고 한다..!

 

 

1) 실제 노드 번호와 방문 순서에 따른 노드 번호

dfs 탐색을 하며 스택에 들어가게 되는 것은 실제 노드 번호이고,

방문 순서에 따른 노드 번호는 부모 노드를 정의하고 계산하기 위해 사용한다.

(초기의 부모 노드는 방문 순서에 따른 노드 번호로 할당한다.)

 

Q. 그럼 실제 노드 번호로 부모 노드를 정의하고 계산할 수는 없을까??

 

 

 

2) SCC 초기값 정의

방문 순서에 따른 노드 번호를 ids 리스트로 관리한다.

ids[i], low_link[i]는 모두 실제 노드 번호 i를 기준으로 저장한다.

id_counter = 0               # 방문 순서를 +1 하기 위한 변수
ids = [0] * (V + 1)          # 각 노드별 방문 순서
low_link = [0] * (V + 1)     # 도달 가능한 가장 낮은 id (부모 노드)

stack = []                   # dfs 스택
on_stack = [False] * (V + 1) # 각 노드별 stack에 있는지 판단

SCC = []                     # SCC 저장 리스트

 

 

3) 미방문 노드에 대한 dfs 실행

for i in range(1, V + 1):
    if ids[i] == 0:
        dfs(i)

 

 

4) dfs 초기 동작

now 노드에 대한 방문 순서를 체크하고, 초기 부모 노드는 방문 순서로 설정한다.

dfs 탐색 과정에서 스택에 실제 노드 번호가 append하여, SCC 집합 원소들을 추적한다.

def dfs(now):
    nonlocal id_counter

    id_counter += 1
    ids[now] = low_link[now] = id_counter

    stack.append(now)
    on_stack[now] = True

 

 

5) dfs 인근 노드 탐색

now 부모 노드는 next 노드의 방문 여부와 next 노드가 스택에 있는 노드인지 에 따라 로직이 달라진다.

 

5-1) next 노드가 미방문 노드일 경우

dfs 탐색을 하며 next 노드의 부모 노드를 찾는다. → low_link[next]를 상위로 전파

탐색이 끝난 후, now 노드에서 도달 가능한 가장 낮은 id 값으로 갱신한다.

(id는 방문 순서에 따른 노드 번호를 의미한다.)

for next in graph[now]:

    # 방문하지 않은 노드라면
    if ids[next] == 0:
        dfs(next)
        low_link[now] = min(low_link[now], low_link[next])

 

5-2) next 노드가 스택에 있는 노드일 경우

now 노드에서 도달 가능한 가장 낮은 id 값으로 갱신한다.

(ids[next]: next 노드의 방문 순서

low_link[next]: next 노드에서 도달 가능한 가장 낮은 id를 뜻한다.)

 

Q1. min을 없애도 되지 않을까?

 

 

Q2. 왜 아래 코드 둘 다 문제 없이 동작할까?

일단 next가 스택에 있다는 것은, 현재 진행중인 DFS 경로 상에 next가 있다는 것을 의미한다.

즉, ids[next]는 현재 발견한 사이클의 시작점 next를 임시 루트로 삼는 것과 같다.

임시 루트로 지정하더라도 min()으로 최소값만 다루기 때문에 문제 없이 동작한다.

 

low_link[next]는 도달 가능한 가장 낮은 id이므로, low_link[next] <= ids[next] 조건이 항상 성립하므로 문제가 없다.

    # 스택에 있는 노드라면
    elif on_stack[next]:
        # 둘 다 문제 없이 동작한다.
        low_link[now] = min(low_link[now], ids[next])      # 1)
        low_link[now] = min(low_link[now], low_link[next]) # 2)

 

 

6) now 노드가 부모 노드일 경우

본인이 부모 노드일 때 스택에서 pop() 하며 SCC 집합을 찾는다.

if ids[now] == low_link[now]:
    scc = []
    while True:
        top = stack.pop()
        on_stack[top] = False
        scc.append(top)

        if top == now:
            break

    scc.sort()  # 정점 번호 오름차순 정렬
    SCC.append(scc)

 

 

전체 코드는 아래의 BOJ - 2150 코드와 같다.

 

 

3. 문제 예시

* BOJ - 2150.Strongly Connected Component (플레 5)

 

[문제]

방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.

 

첫째 줄에 SCC의 개수 K를 출력한다.

다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다.

각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.

 

[코드]

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

def tarjan():
    def dfs(now):
        nonlocal id_counter

        id_counter += 1
        ids[now] = low_link[now] = id_counter

        stack.append(now)
        on_stack[now] = True

        for next in graph[now]:

            # 방문하지 않은 노드라면
            if ids[next] == 0:
                dfs(next)
                low_link[now] = min(low_link[now], low_link[next])

            # 스택에 있는 노드라면
            elif on_stack[next]:
                low_link[now] = min(low_link[now], low_link[next])


        if ids[now] == low_link[now]:
            scc = []
            while True:
                top = stack.pop()
                on_stack[top] = False
                scc.append(top)

                if top == now:
                    break

            scc.sort()  # 정점 번호 오름차순 정렬
            SCC.append(scc)


    id_counter = 0
    ids = [0] * (V + 1)  # 노드별 방문 순서
    low_link = [0] * (V + 1)  # 도달 가능한 가장 낮은 id

    stack = []  # dfs 스택
    on_stack = [False] * (V + 1)

    SCC = []  # SCC 저장 리스트

    """ 미방문 노드에 대해 DFS 수행 """
    for i in range(1, V + 1):
        if ids[i] == 0:
            dfs(i)

    SCC.sort(key=lambda x: x[0])
    return SCC



# 입력 처리
V, E = map(int, input().split())
graph = [[] for _ in range(V + 1)]

for _ in range(E):
    a, b = map(int, input().split())
    graph[a].append(b)

# SCC 찾기
result = tarjan()

# 출력
print(len(result)) # SCC 개수
for scc in result:
    print(*scc, -1)

 

[풀이]

위의 '2. 코드 이해' 설명과 같다.

 

 

4. 문제 적용

1) BOJ - 10265.MT (플레 3)

 

[문제]

각 사람이 원하는 같이 갈 사람이 주어질 때, 버스에 태울 수 있는 사람은 최대 몇 명인지 알아내시오.

(xi는 xi번째 사람이 버스에 타지 않는다면, i번째 사람 역시 버스에 타지 않는다.)

 

[코드]

 

[풀이]

xi번째 사람이 부모, i번째 사람이 자식이라고 생각하면 편하다.

자식은 부모가 안 가면 안 간다. 하지만 부모가 간다고 해도, 자식은 안 갈 수 있다.

그러면 자식이 가기 위한 필수조건은 부모가 가는 것이기 때문에, 부모 → 자식으로 연관관계를 걸어두는 것이 맞다.

(진입차수라고 생각하면 편하다.)

 

 

 

저작자표시

'Algorithm' 카테고리의 다른 글

Stack 알고리즘  (3) 2024.09.21
[백준] 9019번 DSLR _ Python  (0) 2024.03.05

티스토리툴바