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

🥕 [ 백준 10942 ] 팰린드롬?

문제 링크

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

 

🍒 문제 분석

그래프 유형 1. 도넛

- n개의 정점과 n개의 간선

- cycle 이룸

 

그래프 유형 2. 막대

- n개의 정점과 n-1개의 간선

- 출발점과 도착점 존재

 

 

그래프 유형 3. 8자 그래프

- 2n + 1의 정점과 2n+2개의 간선

- 2개의 도넛이 정점을 하나 씩 두고 결합 ( 2 개 Cycle )

 

 

입출력 예

답안) [ 정점 번호, 도넛 수, 막대 수, 8자 수 ]

 

그래프 들을 연결하는 정점 좌표와, 각 그래프들의 개수를 구하는 문제.

 

🍓 내 해결 과정

너무 오랜만에 문제를 푸려니 어떻게 풀어야할지 모르겠어서 아래의 블로그를 참고하였습니다.

https://young-library.tistory.com/204

 

1. 정점이 무엇인지 알아야한다.

   - 정점은 들어오는 간선이 없고, 나가는 간선이 그래프 개수 만큼인 점이다.

   - 막대 그래프에서도 이와 같은 점이 있는데, 단 정점은 나가는 선이 2개 이상이고 막대는 1개 이기 때문에 다르다.

2. 그래프의 개수를 세는 문제이다.

   - 각 그래프가 어떤 형태인지 어떻게 알 수 있을까?

 

 

 

 

 

그래프의 마지막에 어디로도 나가지 않는 정점이 있으면 막대그래프이다. (막대 그래프의 유일한 특성)

 

 

 

 

 

8자 그래프의 경우,. 두 개의 도넛 그래프를 이은 것이기 때문에

정점이 존재한다. 그리고 그 정점은 나가는 간선이 두개 ( 그래프가 2개 이기 때문에 ) 이다.

도넛 그래프에 또한 포함되기 때문에 들어오는 간선이 2개 이다.

(8자 그래프의 유일한 특성)

 

+ in 3, out 2 또한 포함된다. (왜냐면 생성점에서 들어오는 케이스)

 

 

 

 

도넛 그래프는 그 외에 해당한다.

관계도를 알 필요 없이, 단순히 각 노드의 in, out에 대한 간선 수만 알면 풀 수 있는 문제로 바뀌었다.

 

 

 

🥑 코드

from collections import defaultdict 
def solution(edges):
    # 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수
    answer = [0, 0, 0, 0]
    # in, out
    cnt_dict = defaultdict(lambda : [0, 0])
    
    for edge in edges:
        a, b = edge
        cnt_dict[b][0] += 1
        cnt_dict[a][1] += 1
    
    total_graph_cnt = 0
    for dot in cnt_dict.keys():
        # 생성 정점: in 0, out 그래프 수(>=2)
        if cnt_dict[dot][0] == 0 and cnt_dict[dot][1] >= 2:
            answer[0] = dot
            total_graph_cnt = cnt_dict[dot][1]
            continue
        
        # 막대 그래프: 마지막 정점이 out 0
        if cnt_dict[dot][1] == 0:
            answer[2] += 1
            continue
        
        # 8자 그래프: in 2, out 2 
        if cnt_dict[dot][0] in [2,3] and cnt_dict[dot][1] == 2:
            answer[3] += 1
            continue
    
    answer[1] = total_graph_cnt - answer[2] - answer[3]

    
    return answer

 

🍉 깨달은 점 및 정리

문제는 두 가지 측면으로 쪼갤 수 있었다.

정점의 위치는 어떻게 구할 것이며, 각 그래프는 어떻게 분류할 것인가.

정점의 위치는 문제에서도 힌트가 많이 주어졌었기 때문에 바로 알 수 있었지만

각 그래프에 대한 분류는 특징을 잡아내기 어려웠다. ( 이렇게 풀 수 있을거라 생각을 못했다. )

 

특징을 뽑아내고 나니, 문제는 무척 단순하게 바뀌었다. ( 노드의 in, out 간선 개수만 고려하면 되는 )

 

문제를 어떻게 쪼갤 수 있는지, 그리고 작게 쪼갠 문제로 부터 직관을 얻어낼 수 있는지 가 관건인 문제였다.

 

 

직관이 넓어졌길 바라며.