[프로그래머스] 도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP)

https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

 

생각보다 재미있게 푼 그래프 문제

백준 티어로 치면, 골드5 정도 될 것 같다.

 

막대 그래프 = 1자로 연결된 트리

도넛 그래프 = 사이클 1개인 그래프

8자 그래프 = 사이클이 2개인 그래프

 

이때 각각의 그래프를 식별할 수 있는 특징을 잡아내면 된다.

 

막대 그래프는 사이클이 없다.

도넛 그래프는 사이클이 존재하며, 모든 정점의 out degree 가 1개이다.

8자 그래프는 사이클이 존재하며, 1개 정점의 out degree = 2, 나머지 정점의 out degree = 2 이다.

 

또한 막대 그래프, 도넛 그래프, 8자 그래프를 서로 연결하는 임의의 정점은 자신으로 들어오는 indegree 는 없으면서 out degree는 최소 2인 정점이다. (문제 조건상 막대 그래프, 도넛 그래프, 8자 그래프는 최소 2개 존재한다고 했기 때문이다. 막대 그래프의 시작 정점과 구분할 수 있도록 하기 위해서 이런 조건을 추가한 것 같다.)

 

따라서 다음과 같은 흐름으로 문제를 풀었다.

 

1. 모든 그래프를 연결하는 중간 정점 찾기

이 정점은 in degree = 0, out degree > 1 인 정점이다.

 

2. 중간 정점에서 시작하여 DFS 돌리기

이때 각 DFS 결과로 이 DFS를 시작한 정점이 속한 그래프에 사이클이 있는지, 그 그래프의 최대 out degree 개수는 몇 개 인지 센다.

만약 사이클이 없다면 막대 그래프이고, 사이클이 있는데 out degree의 최대 개수가 1개면 도넛 그래프, 2개면 8자 그래프이다.

 

DFS 결과로 각각의 그래프를 카운팅해서 정답 배열에 추가해주면 된다.

 

주의할 점은 파이썬의 경우, 재귀 깊이가 최대 100만까지 갈 수 있으므로 sys.setrecursionlimit 을 통해 제한을 늘려주어야 한다.

 

import sys
sys.setrecursionlimit(10**6)

visit = [False]*1000001
graph = [[] for _ in range(1000001)]
in_deg = [0]*(1000001)
out_deg = [0]*(1000001)

def DFS(node):
    visit[node] = True
    cycle = False
    max_out_deg = out_deg[node]
    for conn_node in graph[node]:
        if visit[conn_node]:
            cycle = True
        else:
            sub_max_out_deg, sub_cycle = DFS(conn_node)
            cycle = cycle or sub_cycle
            max_out_deg = max(max_out_deg, sub_max_out_deg)
    return max_out_deg, cycle


def solution(edges):
    # 도넛 = 사이클
    # 막대 = 트리
    # 8자 = 2개 사이클
    # 시작하는 정점은 나가는 간선이 2개 이상
    # 시작하는 정점은 들어오는 간선이 반드시 0개
    for start, end in edges:
        graph[start].append(end)
        out_deg[start] += 1
        in_deg[end] += 1

    start_node = 0
    for node in range(1, 1000001):
        if in_deg[node] == 0 and out_deg[node] > 1:
            start_node = node
            break

    g1, g2, g3 = 0, 0, 0
    for next_node in graph[start_node]:
        max_out_deg, cycle = DFS(next_node)
        if not cycle:
            g2 += 1
        elif max_out_deg == 2:
            g3 += 1
        else:
            g1 += 1

    answer = [start_node, g1, g2, g3]
    return answer