[Python] 2150 - Strongly Connected Component (플래티넘5)

1. 문제 설명

2150번: Strongly Connected Component

되게 힘든 싸움이었는데, 재밌는 문제였다.

 

---

2. 아이디어

이번 문제는 SCC를 구현해야 하는데 그래프 상에 사이클로 돌아가는 부분을 찾아내서 묶어야 한다.

그래프가 싸이클인지 아닌지 어떻게 알 수 있을까?

단순히 1에서 출발해서 다시 1로 돌아오는지 확인하는 방법으로는 엉뚱한 범위의 SCC가 형성될 수도 있다.

예를 들어, 1 -> 2 -> 3 까지 갔다가 3에서 1과 4로 간선이 연결되어 있다면...1로 돌아오긴 했는데

자칫하다간 4까지 SCC로 엮여버릴 수 있다.

이걸 해결하기 위한 아이디어 자체는 떠올리기 쉽다. 정방향으로 간 순서로 역방향으로 돌아올 수 있다면,

그 구역은 사이클이라고 볼 수 있다.

과연 그런게 가능할까? 가능하다.

 

역순으로 돌리기 위해서는 2가지 정보가 필요한데 처음 입력 받은 정점 정보를 뒤집은 그래프와

실제로 정방향으로 그래프 순회를 했을 때에 조회한 정점의 순서를 역순으로 정렬한 리스트이다.

(이게 왜 필요한지는 뒤에서 설명.)

 

첫 번째는 입력받을 때 같이 만들어버려도 되고, 나중에 기존의 정보 순서를 뒤집어 버려도 된다.

2번같은 경우에는 굉장히 간단한 방법이 있다. DFS를 돌려버리면 된다.

깊이 우선으로 그래프를 순회하다가 재귀를 빠져나오는 과정에서 정점 위치를 queue에 push한다.

다만, 한 번 방문한 정점에 대해서는 방문처리를 함으로써 무한 반복에 빠지지 않도록 유의한다.

이 과정을 1에서 N+1까지 반복해야 하는데 간선이 연결 안 된 정점이 있을 수 있기 때문에 꼭 다 확인해야 한다!

 

지금까지 얻어낸 정보

아니 왜 stack이라고 써놨지..? FIFO 이므로 스택보단 큐가 맞다.

그렇다고 정말 큐를 import해야 하고 그럴 필요는 없다. 그냥 리스트를 큐처럼 쓰는 것 뿐.

어쨌든 이제 값을 차례로 넣어보자.

 

한 바퀴 돌리면 5 4 1이 방문처리 되면서 SSC에 묶이게 된다.

아직 5만 넣고 돌렸으므로 큐의 4, 1이 실제로 지워지진 않았지만 의미없는 데이터가 된다.

 

두 번째 돌렸을 때의 모습.

SSC가 만들어질 때마다 sort()해서 어디 잘 보관해두면 끝난다.

다만 의문인 점이 왜 굳이 1부터 안 돌리고 큐를 만들어서 돌리는 등의 귀찮은 과정을 수반하느냐?

 

바로 여기서 6과 같은 존재가 문제를 일으킬 수 있다.

1과 2를 순서대로 넣으면 SSC가 아래처럼 묶인다.

 

이런 상황을 방지해주기 위해서 일련의 '데이터 흐름'을 만들어 주어 6처럼 홀로 동떨어진 정점을

자연스레 걸러낼 수가 있게 된다.

 

솔직히 당시에는 휴먼 컴파일로만 판단하고 이게 될까 싶었는데 진짜 되서 나도 놀랐었다.

 

---

3. 코드

import sys

sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def reverse_graph(v, graph):
    rev_graph = [[] for _ in range(v+1)]

    for i in range(1, v+1):
        for j in graph[i]:
            rev_graph[j].append(i)
    return rev_graph

def dfs(node, graph, visited, queue:list):
    visited[node] = 1

    for next_node in graph[node]:
        if visited[next_node] == 0:
            #queue.append(next_node)
            dfs(next_node, graph, visited, queue)
    queue.append(node)

def make_queue(v, graph, visited):
    queue = []

    for node in range(1, v+1):
        if visited[node] == 0:
            dfs(node, graph, visited, queue)
    return queue

def reverse_dfs(node, graph, visited, scc:list):
    visited[node] = 1
    scc.append(node)

    for next_node in graph[node]:
        if visited[next_node] == 0:
            reverse_dfs(next_node, graph, visited, scc)

def check_ssc(queue:list, graph, visited):
    cnt, result = 0, []

    while queue:
        scc = []
        node = queue.pop()
        if visited[node] == 0:
            reverse_dfs(node, graph, visited, scc)
            result.append(sorted(scc))
            cnt += 1
    result.sort()
    return cnt, result

def solution():
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    visited = [0] * (v+1)

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

    queue = make_queue(v, graph, visited)
    graph = reverse_graph(v, graph)
    visited = [0] * (v+1)
    cnt, result = check_ssc(queue, graph, visited)

    print(cnt)
    for i in result:
        for j in i:
            print(j, end=" ")
        print(-1)

solution()