[알고리즘/파이썬] 프로그래머스 - 도넛과 막대 그래프

문제

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

프로그래머스

 

풀이

그래프 관련 문제라기보단 단순 구현 문제이다.

이 문제에서 필요한건... 각 노드의 진입차수와 진출차수 이다.

 

생성된 노드 - 진입차수 0, 진출 차수 2 이상인 노드

막대 그래프 - 진입차수가 0인 노드가 있는 그래프

8자 그래프 - 진입 차수 2, 진출 차수 2인 노드가 있는 그래프

도넛 그래프 - 생성된 노드의 진출 차수(전체 그래프의 개수) - (위에서 구한 막대 그래프 개수 + 8자 그래프의 개수)

 

코드

내 풀이

from collections import deque
def solution(edges):
    answer = [0,0,0,0]
    
    outdegree = {}
    indegree = {}
    graph = {}
    
    root = 0
    
    for s,e in edges:
        if s in outdegree.keys():
            outdegree[s] += 1
        else:
            outdegree[s] = 1
            
        if e in indegree.keys():
            indegree[e] += 1
        else:
            indegree[e] = 1
            
        if s in graph.keys():
            graph[s].append(e)
        else:
            graph[s] = [e]

    for a in outdegree.keys():
        if outdegree[a] >= 2 and a not in indegree.keys():
            root = a
            break
        
    def find_node(x):
        q = deque()
        q.append(x)
        
        is_back = False
        is_more_2_out_node = False
        
        visited = set()
        while q:
            nx = q.popleft()
            
            if nx in visited:
                is_back = True
                break
            
            if nx in outdegree.keys() and outdegree[nx] == 2:
                is_more_2_out_node = True
                break
    
            visited.add(nx)
            
            if nx in graph.keys():
                for next in graph[nx]:
                    q.append(next)
                
        if is_more_2_out_node:
            return 3
        if is_back:
            return 1
        return 2
                
    for a in graph[root]:
        result = find_node(a)
        answer[result] += 1
        
    answer[0] = root
        
    return answer

다른 사람 풀이

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