[프로그래머스]Lv2. 도넛과 막대그래프(Python)

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

프로그래머스

 

문제 접근 

 

생성한 정점의 정의가 잘 이해가지 않아 주어진 예시를 그림을 통해 나타내어 보았다. (이미 제시되어 있음..ㅋ)

 

생성한 정점이란?

1. 그래프들과 무관

2. 각 그래프의 임의의 정점 하나로 향하는 간선이 존재

 

 

1번 예시의 경우,

그래프들과 무관한 정점은 2번

도넛 모양 그래프는 1개, 막대 모양 그래프는 1개, 8자 모양 그래프는 0개 => [2, 1, 1, 0]

 

2번 예시의 경우,

그래프들과 무관한 정점은 4번

도넛 모양 그래프는 0개, 막대 모양 그래프는 1개, 8자 모양 그래프는 2개 => [4, 0, 1, 2]

 

풀이 설계(스스로 풀지 못함!!ㅠㅠ)

각 그래프를 판별할 수 있는 조건을 찾아야 한다.

 

1. '생성된 정점'은 나가는 간선의 수가 2개 이상이고, 들어오는 간선의 수가 0

2. '막대 모양 그래프'의 수는 나가는 간선의 수가 0, 들어오는 간선의 수가 1이상 (생성된 정점에서 들어오는 간선 고려)

3. '8자 모양 그래프'의 수는 나가는 간선의 수가 2, 들어오는 간선의 수도 2이상 (생성된 정점에서 들어오는 간선 고려)

4. '도넛 모양 그래프'의 수는 '생성된 정점'의 나가는 간선 수 - (막대 모양 그래프 + 8자 모양 그래프) 

 

=> 확실한 건 도넛 모양 그래프의 수를 조건으로 작성하는 것은 별로 좋은 생각은 아님..

=> 도넛 모양의 그래프의 수를 구하려면 생성된 정점은 무조건 도넛, 막대, 8자 모양 그래프 중 하나와 연결

코드

def solution(edges):
    answer = []
    # edges의 요소를 순회하면서 각 노드별로 들어오는 간선, 나가는 간선의 개수를 체크하는 함수
    def count_edges(edges):
        edges_counts = {}   # 각 노드별로 간선의 수를 추가할 딕셔너리 
        for a, b in edges:
            if edges_counts.get(a) == None:
                edges_counts[a] = [0, 0]    # value의 구조 [나가는 간선, 들어오는 간선]
            if edges_counts.get(b) == None:
                edges_counts[b] = [0, 0]
            
            # 나가는 간선, 들어오는 간선의 개수를 추가
            edges_counts[a][0] += 1
            edges_counts[b][1] += 1
        
        return edges_counts
    # 모든 edges를 순회하며 count_edges를 통해 간선을 체크해서 정답을 찾는 함수 
    def find_answer(edges_counts):
        answer = [0, 0, 0, 0]
        for key, counts in edges_counts.items():
            if counts[0] >= 2 and counts[1] == 0:   # 생성된 정점의 번호 확인 
                answer[0] = key
            elif counts[0] == 0 and counts[1] >= 1: # 막대 그래프의 수 확인 
                answer[2] += 1
            elif counts[0] == 2 and counts[1] >= 2:  # 8자 모양 그래프의 수 확인
                answer[3] += 1
        
        # 도넛 모양 그래프의 수 확인 
        answer[1] = (edges_counts[answer[0]][0] - answer[2] - answer[3])
            
        return answer
    
    edges_counts = count_edges(edges)
    answer = find_answer(edges_counts)
    
    return answer

 

문제 회고

 

참고한 해설에서 8자 모양 그래프의 수를 확인할 때 나가는 간선, 들어오는 간선의 수가 2 이상으로 조건을 설립했다. 하지만 내가 생각하기에 나가는 간선의 수는 2, 들어오는 간선의 수가 2 또는 3일 때에 해당한다고 생각해서 조건문을 수정해서 실행해 보았는데 테케가 통과했다. 왜 해설자가 나가는 간선의 수를 2 이상으로 설정했는지 의문이다..

 

+ 이 문제에서는 그래프의 판별 기준을 노드에서 들어오는 간선, 나가는 간선의 수로 설정하였다.. 앞으로 그래프 문제가 나오면 한번은 무조건 생각해 봐야겠다.