99클럽 코테 스터디 12일차 (프로그래머스 도넛과막대)

오늘의 문제: 프로그래머스 도넛과 막대

문제 설명

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

프로그래머스

알고리즘

문제는 시작 노드에 연결되어 있는 도넛, 막대, 8자 모양 그래프의 개수를 찾는 문제입니다. 시작 노드와 각 그래프에 포함되어 있는 노드는 특징은 다음과 같습니다.

• 시작 노드: 노드에 들어오는 간선이 없고 나가는 간선이 2개 이상인 노드
• 막대 그래프: 나가는 간선이 없는 노드가 포함되어 있는 그래프
• 도넛 그래프: 나가는 간선과 들어오는 간선으 수가 같은 노드가 포함되어 있는 그래프
• 8자 모양 그래프: 나가는 간선과 들어오는 간선의 개수가 2인 노드가 포함되어 있는 그래프

위와 같이 생각한 후에 시작 노드를 처음으로하는 dfs 그래프 탐색을 이용 경로안에 위와 같은 특징의 노드가 존재할 경우 count하는 식으로 처음 코드를 작성 하였습니다. 처음 코드는 시간 초과가 발생하고 도넛 그래프의 특징도 잘못 생각한 코드로 오답을 받았습니다. 질문하기에 있는 다른 분들의 의견을 보고 노드의 특징을 다시 정의 하고 코드를 작성하였습니다.

그래프의 개수만 알면 되기 때문에 총 그래프의 개수가 필요합니다. 또한 막대 그래프는 나가는 간선이 없는 노드를 1개 가지고 있기 때문에 나가는 간선이 없는 노드의 수가 막대 그래프의 수입니다. 8자 모양 그래프의 경우 나가는 간선 과 들어오는 간선이 2개인 노드를 1개 가지고 있기 때문에 막대 그래프와 동일하게 노드의 수가 그래프의 수입니다.

• 시작 노드: 나가는 간선이 2개 이상인 노드(나가는 간선의 수가 총 그래프의 수)
• 막대 그래프: 나가는 간선이 없는 노드의 수가 그래프의 수
• 8자 모양 그래프: 나가는 간선과 들어오는 간선의 개수가 2인 노드의 수가 그래프의 수
• 도넛 그래프: 총 그래프의 수 - 막대 그래프의 수 - 8자 모양 그래프의 수

위와 같이 그래프의 수의 규칙으로 정리후 코드를 다시 작성하였습니다.

def solution(edges):
    answer = []
    node_dic = dict()
    
    # 각 노드의 나가는 간선과 들어오는 간선 수를 기록
    for edg in edges:
        if edg[0] in node_dic:
            node_dic[edg[0]][0] += 1
        else:
            node_dic[edg[0]] = [1, 0]
        if edg[1] in node_dic:
            node_dic[edg[1]][1] += 1
        else:
            node_dic[edg[1]] = [0, 1]

    
    # 결과 리스트 초기화: [센터 노드, 도넛, 막대, 8자]
    answer = [0, 0, 0, 0]
    
    # 조건에 따라 분류
    for key in node_dic:
        out_count, in_count = node_dic[key]

        # 막대 노드: 나가는 간선이 없는 노드
        if out_count == 0:
            answer[2] += 1
        
        # 8자 형태 노드: 나가는 간선과 들어오는 간선이 모두 2개인 노드
        elif out_count == 2:
            if in_count != 0:
                answer[3] += 1
            # 나가는 간선이 2 들어오는 간선이 없는 경우 시작 노드
            else:
                answer[0] = key
        
        # 나가는 간선이 2개이상인 노드는 시작 노드
        elif out_count > 2:
            answer[0]= key

    # 도넛 수 계산: 센터 노드의 나가는 간선 수에서 막대와 8자 개수를 제외
    answer[1] = node_dic[answer[0]][0] - answer[2] - answer[3]
    
    return answer