# 생성된 정점의 번호, 도넛 수, 막대 수, 8자 수
# 정점의 번호: 들어오는 간선 = 0, 나가는 간선 수 >= 2
# 도넛 수: 8자랑 막대 그래프 수 구해서 총에서 빼주기
# 막대 수: 들어오는 간선 1
# 8자 수: 들어오는거 2개, 나가는거 2개
def solution(edges):
answer = [0, 0, 0, 0]
trunk = {}
for a, b in edges: # a: 나가는 간선, b: 들어오는 간선
if a not in trunk:
trunk[a] = [0, 0]
if b not in trunk:
trunk[b] = [0, 0]
trunk[a][0] += 1
trunk[b][1] += 1
for node, item in trunk.items():
give = item[0]
take = item[1]
if give >= 2 and take == 0: # 생성한 정점
answer[0] = node
elif give >= 2 and take >= 2: # 8자 모양
answer[3] += 1
elif give == 0 and take >= 1: # 막대 모양
answer[2] += 1
# 전체 그래프 개수 == 정점에서 나가는 간선의 개수
answer[1] = trunk[answer[0]][0] - answer[2] - answer[3]
return answer 풀이과정
문제를 보고 뇌사가 와서 결국 서칭했다.
풀이는 생각보다 단순했고, 특징을 찾는 문제였다. 자료해석이 중요해보인다.
생각보다 특징은 단순했다.
생성되는 정점의 경우 나가는 간선만 있을뿐 들어오는 간선은 없다.
도넛 그래프부터 특징을 구하려고 했는데 본인한테만 쏠 수도 있고 그래서 특징이 좀 복잡해보였다.
막대 그래프의 특징을 보자. a → b로 노드로부터 나가는 선이 한개씩 있다.
8자 모양 그래프의 경우 나가는 간선이 2개, 들어오는 간선이 2개이다.
그래프 해석
막대그래프의 경우 2번 노드를 보면 4번 노드로부터 간선이 한개만 오고있다. 막대그래프 +=1
8자 모양 그래프의 경우 3, 11번 노드를 봐보자. 들어오는 간선 2개, 나가는 간선 2개로 8자 모양 그래프가 2개가 있다.
생성되는 정점의 경우 4번 노드를 보면 나가는 간선만 있고 들어오는 간선은 없다.
도넛 그래프를 이제 구해야한다. 보시다싶이 도넛 그래프는 찾아볼 수가 없다. 이를 어떻게 구할까?
현재 2번 그림에서 총 그래프는 3개이다. 막대 1개, 8자 모양 2개
총 그래프 3 - 1 - 2를 하면 된다.
총 그래프의 개수는?
생성되는 정점을 보자. 사실 이 부분을 파악하지 못했었다. 웃기게도 보이지가 않았다…
4번 노드를 보면 나가는 간선이 3개이다. 그리고 총 그래프가 3개이다.
생성된 정점으로부터 나가는 간선이 곧 총 그래프의 개수이다.
풀이 후기
간선이 뭐 n개고 n-1개고 이런거에 너무 집착해서 오히려 구렁텅이로 빠졌다.
직관적으로 그림에서 특징을 파악해서 코드를 짜면 되는 문제였다.
계속해서 풀면서 감을 익혀보자.
