프로그래머스 Level 2 | 2024 KAKAO WINTER INTERNSHIP 도넛과 막대 그래프 | Python

kimminjunnn·2025년 10월 12일

프로그래머스

알고리즘

목록 보기

202/322

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

문제 파악

도넛 모양 그래프

도넛 모양 그래프에 대해 설명하고 있다.
도넛 모양 그래프는 n개의 정점, n개의 간선. 즉 정점의 수와 간선의 수가 일치하는 특징을 가진다.
그리고 n-1 개의 정점들을 방문하고, 자기 자신으로 돌아오는 특징을 가진다.
어느 정점에서 출발해도 자기 자신으로 돌아오는 성질이 있다.

막대 모양 그래프

막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있다.
막대모양 그래프는 특정 정점에서 출발해야 n-1개의 정점을 방문할 수있다.

8자 모양 그래프

8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있다.
즉 정점은 n이 커짐에 따라 3,5,7... 순으로 두개씩 커지고, 정점은 4,6,8,... 순으로 커진다.

또한 8자 모양 그래프는 n이 같은 2개의 도넛 모양 그래프에서 특정 정점을 골라 두개를 결합시킨 형태의 그래프라고 한다.

문제에서 요구하는 것

도넛, 막대, 8자 모양의 그래프가 여러개 있고, 이 그래프와 무관한 정점을 하나가 있는데
이 무관한 정점에서 각 그래프의 임의의 정점 하나로 향하는 간선을 연결 했다고 한다.
그 후 그 정점들에 대해 서로 다른 번호를 매겼다.

그래프의 간선 정보 edges가 주어졌을 때, 생성한 정점의 번호와 정점을 생성하기 전 도넛,막대,8자 모양의 그래프 수를 구해야 한다고 한다.

예시를 통해 흐름을 보자

예제 1

edges = [[2,3],[4,3][,[1,1],[2,1]]

주어진 edges 를 그림으로 나타내면 위 그림과 같다.
[[1,1]] 이 도넛 모양 그래프,
[[4,3]] 이 막대모양 그래프 이다.
2번 정점이 그래프와 상관없이 임의 생성한 정점인 듯 하다.

답은 [생성한 정점 번호, 도넛 모양 그래프 개수, 막대모양 그래프 개수, 8자 모양 그래프 개수] 를 return 해주어야 하니 [2,1,1,0] 을 return 하면 된다.

예제 2

edges = [[4, 11], [1, 12], [8, 3], [12, 7], [4, 2], [7, 11], [4, 8], [9, 6], [10, 11], [6, 10], [3, 5], [11, 1], [5, 3], [11, 9], [3, 8]]

주어진 edge를 그리면 위 모양 그래프가 된다.
4번이 생성한 정점이고,
막대가 4->2 그래프 한개
8자 그래프가 좌측에 8-3-5, 우측에 11을 중심으로 한 그래프 해서 총 두 개이다.
도넛 모양 그래프는 8자 모양 그래프에 포함되기에 카운팅 하지 않나보다. 2개로 보이지만 이는 8자그래프에 일부분으로 보는 것 같다.

따라서 [4,0,1,2] 를 return 해준 모습이다.

해결 아이디어

이 문제는 그래프의 구조(형태) 자체를 분석해야 하는 유형이다.
진입 차수(in_degree) 와 진출 차수(out_degree)를 통해 모양을 판별할 수 있다.

도넛형 그래프 (Donut)

하나의 사이클(원)로 연결
예: 1 → 2 → 3 → 1
특징:
- 모든 노드의 진입 차수가 진출 차수와 동일하다.
- 모든 노드의 in-degree == 1
- 모든 노드의 out-degree == 1

막대형 그래프 (Bar)

일방향으로 쭉 연결된 형태
예: 1 → 2 → 3 → 4
특징:
- 시작,끝,나머지 노드의 진입/진출 차수가 다르다.
- 시작 노드: in-degree == 0, out-degree == 1
- 끝 노드: in-degree == 1, out-degree == 0
- 나머지: in-degree == 1, out-degree == 1

8자형 그래프 (Figure-8)

두 개의 사이클이 한 노드에서 합쳐진 형태
예: 1 → 2 → 3 → 1 과 1 → 4 → 5 → 1
특징:
- 합쳐지는 노드(교차점): in-degree ≥ 2, out-degree ≥ 2

임의 생성한 노드 찾는 법

생성한 노드는 이 노드로 들어오는 진입 차수가 없다.
문제에서 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다. 라고 했기에 진출 차수는 무조건 2 이상이다.

해답 및 풀이

def solution(edges):
    # 간선에 등장한 노드 번호의 최댓값을 먼저 구한다.
    max_node = 0
    
    for a, b in edges:
        if a > max_node:
            max_node = a
            
        if b > max_node:
            max_node = b
        
    # indeg[n] : n으로 들어오는 간선의 개수
    # outdeg[n] : n으로 나가는 간선의 개수
    # exist : 입력에 실제 등장한 노드인지 표시
    
    indeg = [0] * (max_node + 1)
    outdeg = [0] * (max_node + 1)
    exist = [False] * (max_node + 1)
    
    # 간선 순회하며 차수 집계
    # indeg,outdeg +1 해주고 exist True로
    for a, b in edges:
        outdeg[a] += 1 # a에서 나가는 것임
        indeg[b] +=1 # b로 들어옴
        exist[a], exist[b] = True, True
    
    # 생성한 노드 찾기
    # 생선한 노드는 진입 차수가 없다.
    # 생성한 노드는 진출 차수가 2 이상이다.
    new_node = -1
    for n in range(1,max_node+1):
        if not exist[n]:
            continue
        if indeg[n] == 0 and outdeg[n] >= 2:
            new_node = n
            break
    
    # 본격 도넛, 막대, 8자 그래프 개수 세기
    donut = 0
    bar = 0
    eight = 0
    
    for n in range(1, max_node + 1):
        if not exist[n] or n == new_node: # n번 노드가 존재하지 않거나, new_node 라면 건너뛰고 다음 반복문으로
            continue
            
        # 이러한 노드를 찾으면 막대 그래프가 있는 것이기에 bar += 1
        if outdeg[n] == 0 and indeg[n] >= 1:
            bar += 1
        
        # 이러한 노드를 찾으면 8자 그래프가 있는 것이기에 eight += 1
        elif outdeg[n] >= 2 and indeg[n] >= 2:
            eight += 1
        
    # 도넛 막대는 8자형에 포함되어있기에 in,out 차수로 구하기 어렵다.
    # 그래서 센스로 new_node에서 뻗는 그래프에서 bar,eight을 빼주면 남은 것은 바로 donut 뿐이다.
    donut = outdeg[new_node] - bar - eight
    
    answer = [new_node,donut,bar,eight]
    
    return answer