(프로그래머스 Lv.2) 도넛과 막대 그래프

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258711

코드

주석은 내가보려고 달아놓음

def solution(edges):
    answer = [0, 0, 0, 0]
    
    # edges는 이중리스트로 주어진다.
    # 이 문제에서 찾아야 할 건 그래프 안의 node 값이 아니라,
    # 각 노드에서 간선이 몇 번 빠져나가고 들어갔는지가 중요함.

    # 간선을 그리기 위해
    # row(행)에서 가장 큰 값이 있는 인덱스를 찾고, (e.g [[2, 3], [4, 3], [1, 1], [2, 1]] 일 때 [4,3] )
    # 앞서 구한 row 중 큰 값이 있는 column(열)을 찾는다. (== 4)
    # 그러고 인덱스 0번째 값은 사용하지 않으니 이 값에 + 1. (== 5)
    max_val = max(map(max, edges)) + 1
    # max_node = -1
    # for edge in edges:
    #     for node in edge:
    #         if node > max_node:
    #             max_node = node
    # max_val = max_node + 1 # 5
        
    # 각 노드에서 in/ out 간선이 몇 개인지 구한다.
    in_cnt, out_cnt = [0] * max_val, [0] * max_val
    for now_out, now_in in edges:
        out_cnt[now_out] += 1
        in_cnt[now_in] += 1
    print(out_cnt)
    print(in_cnt)

    for now_node in range(1, max_val):
        # 생성된 정점이라는건, 루트 노드(모든 노드의 뿌리)를 말한다.
        # 따라서 들어오는 간선은 없는데, 나가는 간선만 존재한다면 루트 노드를 의미한다.
        if in_cnt[now_node] == 0 and out_cnt[now_node] >= 2:
            answer[0] = now_node
        # 막대 모양 그래프는 리프 노드로 판별 할 수 있으며, 
        # 들어오는 간선만 있고 나가는 간선은 없다면 막대 그래프라고 할 수 있다. (<-> 루트 노드와 반대)
        elif in_cnt[now_node] >= 1 and out_cnt[now_node] == 0:
            answer[2] += 1
        # 반대로 8자 모양 그래프에 해당하는 노드는,
        # 들어오는 간선이 2개 이상이고 나가는 간선 또한 2개 이상일 때 8자 모양 그래프라고 할 수 있다.
        elif in_cnt[now_node] >= 2 and out_cnt[now_node] == 2: 
            answer[3] += 1
    # 마지막으로 도넛 모양 그래프는, 순환 그래프라서 모든 노드에서 간선이 1개씩 들어오고 나가는 형태다.
    # 따라서 도넛 모양 그래프 개수 = (루트 노드의 간선 - (막대 그래프 개수 + 8자 그래프 개수))
    # ★ 도넛 모양 그래프는 단일 순환 그래프여야 된다. 노드 하나에서 순환되는 과정이 2개 이상 존재한다면 그건 8자 모양 그래프다.
    # Q. 왜 이렇게 구하면 안될까?
        # elif in_cnt[now_node] == 1 and out_cnt[now_node] == 1:
            # answer[1] += 1
    # => 막대그래프에서 연결되는 노드가 위의 조건에 해당할 수 있기 때문에 안된다.
    answer[1] = out_cnt[answer[0]] - sum(answer[2:])
    
    return answer

print(solution([[2, 3], [4, 3], [1, 1], [2, 1]]))

풀이

일단 문제에서 주어진 그래프들의 각 특징을 찾아보자.

이 문제에선 그래프 안에 있는 node값이 중요한게 아니라, 각 노드마다 들어오고 나가는 간선이 몇 개인지 보는게 중요하다.

일단 그래프 사진을 보고 규칙을 찾아보자.

• 도넛 그래프는 노드에 나가는 간선이 1개, 들어오는 간선이 1개.
• 막대 그래프는 리프 노드(맨 마지막 노드) 기준 들어오는 간선만 1개 이상.
• 8자 모양 그래프는 노드에서 들어오는 간선이 2개 이상, 나가는 간선도 2개 이상.

규칙을 구했으니 예시 그래프에서 루트 노드는 뭐고, 도넛, 막대, 8자가 각각 몇 개 있는지 구해보자. 발글씨 죄송

• 1: 나가는 간선 1개, 들어오는 간선 2개.
  • 근데 그림을 딱 봤을 때 노드 1은 단일 순환을 하니까 도넛 모양 그래프에 해당하잖아.
  • 근데 앞에서 도넛 모양 그래프는 각 노드에서 나가는 간선이 1개, 들어오는 간선이 1개라며.
  • 그렇다면 도넛 모양 그래프는 if문이 아니라, (루트 노드 간선 개수 - (막대 모양 그래프 개수 + 8자 모양 그래프 개수)) 로 구해야 되겠네?
  • 왜? 루트 노드 간선때문에 도넛 모양 그래프라고 인식을 못하는거잖아. 그러니 나머지 종류(막대, 8자)그래프 개수 합을 구하고, 그 값에 루트 노드 간선 개수를 빼면 도넛 모양 그래프 개수가 될 것.
• 2: 나가는 간선만 2개.
  • 나가는 간선만 있으니까 얘가 루트 노드(시작 정점) 이겠네.
• 3: 들어오는 간선만 2개.
  • 얘는 나가는 간선 없이 들어오는 간선만 있으니까 막대 그래프의 리프노드가 되겠다.
• 4: 나가는 간선만 1개.
  • 3이랑 연결되는 막대그래프에 해당하네. 그러니 저 그래프에서의 루트노드는 2, 도넛 그래프는 1개, 막대 그래프는 1개, 8자는 0개가 되겠네.

다른 그림도 위 공식을 사용해서 봐보자.

• 1: 나가고 들어오는 간선이 각각 1개씩 존재하네.
• 2: 들어오는 간선만 1개 존재하네.
• 3: 나가고 들어오는 간선이 2개 이상이네. 8자 그래프 당첨
• 4: 나가는 간선만 3개네. 루트 노드 당첨
• 6: 1이랑 같음
• 7: 1, 6이랑 같음
• 8: 들어오는건 2개고 나가는건 1개네
• 9: 1, 6, 7 이랑 같음
• 10: 1, 6, 7, 9랑 같음
• 11: 들어오는게 2개 이상(== 3개) 나가는건 2개네. 8자 당첨
• 12: 1, 6, 7, 9, 11이랑 같음.

도넛 그래프 개수만 (루트 노드 간선 개수 - (막대 모양 그래프 개수 + 8자 모양 그래프 개수)) 이렇게 구하는게 맞겠구나.

하고 코드 짜면 됨

은 하루 걸려서 이해함. 직접 푼 것도 아님. 세상에 똑똑한 사람이 너무 많다.