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

문제

여러개의 정점이 있고, 간선의 정보가 주어진다. [a, b]는 a->b로 이어져있다는 뜻이다.
간선을 모두 이었을 때 도넛, 막대, 8자 3종류의 그래프와 생성 정점이 생긴다.
이 때 생성 정점과 각 종류 그래프의 개수를 구하여라.
단, 모든 종류의 그래프가 항상 존재하지는 않지만 그래프는 최소 2개 이상 보여진다.

ex)

edges = [[2, 3], [4, 3], [1, 1], [2, 1]]
result = [2, 1, 1, 0] # [생성점, 도넛개수, 막대개수, 8자개수]

풀이

주어진 입력을 가지고 그림을 그려보면 특징을 발견할 수 있다.
각 특징을 살펴보자.

1. 생성점 -> 들어오는 간선 수 = 0 // 나가는 간선 수 >= 2
2. 막대그래프 개수 -> 나가는 간선 없이 들어오는 간선 수가 1개인 정점의 수
3. 8자그래프 개수 -> 들어오는 간선, 나가는 간선 수가 각각 2개 이상인 정점의 수
4. 도넛그래프 -> 나머지 그래프

자세한건 코드에서 알아보자

전체코드

def solution(edges):
    answer = [0, 0, 0, 0]

    exchangeCnts = {}
    for a, b in edges:
        if not exchangeCnts.get(a):
            exchangeCnts[a] = [0, 0]
        if not exchangeCnts.get(b):
            exchangeCnts[b] = [0, 0]
        
        # 준 것, 받은 것 카운팅
        # a, b는 a가 b에 준 것, b가 a에게 받은 것
        exchangeCnts[a][0] += 1
        exchangeCnts[b][1] += 1
    
    for key, exchangeCnt in exchangeCnts.items():
        # 그래프는 최소 2개 이상으로 준 것만 2개 이상인 정점이 생성점
        if exchangeCnt[0] >= 2 and exchangeCnt[1] == 0:
            answer[0] = key
        # 받은 것만 있는 정점의 개수는 막대 그래프의 개수
        elif exchangeCnt[0] == 0 and exchangeCnt[1] > 0:
            answer[2] += 1
        # 준 것, 받은 것 각각 2개 이상인 점의 개수는 8자 그래프의 개수
        elif exchangeCnt[0] >= 2 and exchangeCnt[1] >= 2:
            answer[3] += 1
    
    # 전체 그래프 개수인 생성점의 준 것에서 2종류의 그래프를 빼면 도넛 그래프의 개수
    answer[1] = (exchangeCnts[answer[0]][0] - answer[2] - answer[3])

    return answer