[프로그래머스] 도넛과 막대 그래프
🥕 [ 백준 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 간선 개수만 고려하면 되는 )
문제를 어떻게 쪼갤 수 있는지, 그리고 작게 쪼갠 문제로 부터 직관을 얻어낼 수 있는지 가 관건인 문제였다.
직관이 넓어졌길 바라며.