[Python] 도넛과 막대 그래프

[프로그래머스] 도넛과 막대 그래프

• 문제 출처: 프로그래머스
• 난이도: level 2
• 참고: 2024 KAKAO WINTER INTERNSHIP
• input size: $1 \le V, \ E \le 10^6$
• (주관) 자료구조: 그래프, 리스트
• (주관) 알고리즘: 그래프, 차수(degree) 개념
• (주관) 예상 시간복잡도: $O(V+E) = O(10^6)$

오랜만에 코테 준비로 프로그래머스 접속했는데, 문제가 굉장히 많아졌다.

2년전에 코테 준비할 때 거의 다 푼 것같은데 그새 못푼 문제가 많이 쌓였다.

 

처음 이 문제를 봤을때 수없이 많은 루프에 정신이 나갔다.

처음에 BFS/DFS로 모든 노드를 순회하면서 그래프의 특징을 찾으려 하다가(예: 탐색을 마친 그래프의 노드 개수가 n개고 edge 개수가 n-1이면 막대그래프로 판정) "루프가 너무 많은 거 아닌가? DFS/BFS가 아니지 않을까?" 하다가 패턴을 알아냈다.

 

STEP 1. 생성한 정점 알아내기

그래프를 만드는 순서로는 그래프를 만들고, 생성 정점을 만들고, 무작위 넘버링을 해주었다고 한다.

그런데 문제를 풀 때도 이 순서대로 따라갈 이유는 없다.

왜냐면 이미 parameter로 고정된 문제 상황이 주어지기 때문이다.

따라서 생성한 정점을 먼저 알아낼 것이다. (이것을 알아내는게 가장 쉽고, 나머지 단계의 힌트가 된다.)

 

생성한 정점은 들어오는 화살표는 없고, 나가는 화살표만 존재한다.

그리고 그래프의 개수는 2 이상임이 보장되므로(문제 설명 참고), 나가는 화살표는 항상 2개 이상이다.

유식한 말로 진입차수=0, 진출차수 >= 2이다.

 

아~ 그러니까 이 문제는 각 노드의 진입/진출차수를 표현할 데이터가 필요하겠구나~

indegree, outdegree를 표현해줄 리스트를 만들어서 생성된 정점(gen_node라 이름지었다)을 찾아보자.

max_node = 0
for src, dst in edges:
    max_node = max(max_node, src, dst)

indeg = [0] * (max_node + 1)
outdeg = [0] * (max_node + 1)

for src, dst in edges:
    indeg[dst] += 1
    outdeg[src] += 1
        
gen_node = -1
num_d, num_stick, num_eight = 0, 0, 0
for i in range(1, max_node + 1):
    if indeg[i] == 0 and outdeg[i] >= 2:
        gen_node = i

 

STEP 2. 각 그래프의 특징을 알아내자

크기가 n인 도넛 그래프 (출처: 프로그래머스)

 

n개의 정점과 n개의 간선.... 이런 정보는 이제 더이상 도움이 되지 않는다.

왜냐면 그래프 순회를 할 것이 아니기 때문이다.

앞서 생성된 정점을 찾는데 in/out degree라는 정보를 이용했으니, 이것도 똑같이 찾아보자.

 

도넛 그래프의 정점들은 진입차수와 진출차수 모두 1이다.

음... 아직 잘 모르겠다.

일단 여기까지만 알아두고 다른 그래프의 특징을 알아보자.

크기가 n인 막대 그래프 (출처: 프로그래머스, 수정: 필자)

 

막대그래프의 정점의 맨끝점은 진입차수가 1이고 진출차수가 0이다.

가운데 연결된 노드들은 진입차수와 진출차수가 모두 1이다. 

우리는 막대그래프의 개수를 찾고싶으니까 진출차수가 0인 노드를 찾으면 될 것 같다. ^^

물론 생성된 노드에서 임의의 정점에 연결되는 간선이 있을 수 있다.

그렇지만 진출차수가 0인 노드의 개수를 찾는 것은 변하지 않는다.

크기가 n인 8자 그래프 (출처: 프로그래머스, 편집: 필자)

 

8자 그래프의 특징은 중심이 되는 노드(도넛 그래프가 만나는 지점)의 진입차수와 진출차수가 모두 2라는 점이다.

물론 생성된 노드에서 임의의 정점에 연결되는 간선이 있을 수 있다.

따라서 8자 그래프의 개수는 진입차수가 2 이상이고 진출차수가 2인 노드의 개수와 동일하다.

gen_node = -1
num_d, num_stick, num_eight = 0, 0, 0
for i in range(1, max_node + 1):
    if indeg[i] == 0 and outdeg[i] >= 2:
        gen_node = i
    if indeg[i] > 0 and outdeg[i] == 0:
        num_stick += 1
    if indeg[i] >= 2 and outdeg[i] == 2:
        num_eight += 1

 

이제 도넛 그래프의 개수를 찾아보자.

도넛 그래프의 개수가 찾기 어려운 이유는 생성된 노드와 연결된 노드의 진입/진출 차수가 [2, 1]이 되어서 특징이 없어지기 때문이다. 

그런데 문제 상황에서 항상 생성된 노드와 연결된 그래프 개수는 전체 그래프 개수와 동일하다.

왜냐면 그래프를 먼저 만들어놓고, 생성된 정점에서 연결시켰기 때문이다.

그러니까 생성된 노드와 연결된 서로 다른 노드가 같은 그래프에 있지 않다는 것이다.

그러면 도넛 그래프의 개수는 (생성 노드의 진출차수) - {(막대 그래프 개수) + (8자 그래프 개수)}이다.

num_d = outdeg[gen_node] - (num_stick + num_eight)

 

 

완성된 코드는 다음과 같다.

def solution(edges):
    answer = []
    max_node = 0
    for src, dst in edges:
        max_node = max(max_node, src, dst)
    
    indeg = [0] * (max_node + 1)
    outdeg = [0] * (max_node + 1)
    
    for src, dst in edges:
        indeg[dst] += 1
        outdeg[src] += 1
        
    gen_node = -1
    num_d, num_stick, num_eight = 0, 0, 0
    for i in range(1, max_node + 1):
        if indeg[i] == 0 and outdeg[i] >= 2:
            gen_node = i
        if indeg[i] > 0 and outdeg[i] == 0:
            num_stick += 1
        if indeg[i] >= 2 and outdeg[i] == 2:
            num_eight += 1
    num_d = outdeg[gen_node] - (num_stick + num_eight)
    
    answer = [gen_node, num_d, num_stick, num_eight]
    return answer

 

노드 개수를 V, 엣지 개수를 E라 하면 내 시간복잡도는 $O(V+E)$이다.

$V, E \le 10^6$이므로 충분하다.

 

참고. 실행 속도와 메모리

실행속도와 메모리