문제

Programmers 도넛과 막대 그래프

설명: 1자, 8자, 도넛 그래프가 주어지고 이 모든 그래프와 연결되는 노드 1개가 주어질 때 이 노드와 1자, 8자, 도넛 그래프의 개수를 구하라

풀이

각 그래프의 내차수(indegree), 외차수(outdegree)의 관점에서 생각해보자
기본적으로 내차수가 0이고 외차수가 2이면 모든 그래프와 연결된 노드이다.
1자 그래프의 시작점은 내차수가 0이고 외차수가 1개 이하이다.
8자 그래프의 중간점은 외차수가 2개이다.
이외는 도넛 그래프이다.
따라서 모든 그래프와 연결된 노드를 가장 먼저 구해주고, 1자, 8자 그래프의 시작점을 구한 뒤, 이 점에서 탐색을 하며 만난 노드들을 지워준다
마지막으로 탐색을 한적 없는 노드는 모두 도넛 그래프이다.
추가적으로 8자 그래프는 단순 DFS를 하면 한쪽 방향밖에 탐색할 수 없으므로 두 방향 모두 탐색해준다.

오늘의 회고

아무리 해도 맞게 구현했는데 python의 재귀 한계에 도달해서 런타임 에러가 발생했다.
sys.setrecurionlimit을 노드의 최대인 $10^6$으로 설정해주어 해결했다.
- 디폴트 값은 $1,000$이다.

Code

# Programmers258711.py
import sys
sys.setrecursionlimit(10 ** 6)

MAX_NODE = 1_000_001

visited = [False] * MAX_NODE
adj_list = [[] for _ in range(MAX_NODE)]

def dfs(curr):
    if adj_list[curr]:
        next_node = adj_list[curr][0]
        if not visited[next_node]:
            visited[next_node] = True
            dfs(next_node)

def solution(edges):
    ans = [0, 0, 0, 0]

    n = 0
    is_node = [False] * MAX_NODE
    indegree, outdegree = [0] * MAX_NODE, [0] * MAX_NODE
    for u, v in edges:
        n = max(n, u, v)

        is_node[u] = True
        is_node[v] = True

        adj_list[u].append(v)
        outdegree[u] += 1
        indegree[v] += 1

    for i in range(1, n + 1):
        if indegree[i] == 0 and outdegree[i] >= 2:
            ans[0] = i
            for adj in adj_list[i]:
                indegree[adj] -= 1
            break

    stick, graph8 = [], []
    for i in range(1, n + 1):
        if is_node[i] and indegree[i] == 0 and outdegree[i] <= 1:
            stick.append(i)
        elif indegree[i] == 2 and outdegree[i] == 2:
            graph8.append(i)

    for i in stick:
        visited[i] = True
        dfs(i)
        ans[2] += 1

    for i in graph8:
        visited[i] = True
        visited[adj_list[i][0]] = True
        visited[adj_list[i][1]] = True

        dfs(adj_list[i][0])
        dfs(adj_list[i][1])

        ans[3] += 1

    visited[ans[0]] = True
    for i in range(1, n + 1):
        if is_node[i] and not visited[i]:
            visited[i] = True
            dfs(i)
            ans[1] += 1

    return ans