프로그래머스 2024 KAKAO WINTER INTERNSHIP 도넛과 막대 그래프 문제 풀이(Python, 구현, DFS)

프로그래머스 2024 KAKAO WINTER INTERNSHIP 도넛과 막대 그래프 문제 바로가기

문제 접근

이 문제를 푸는 방법은 크게 3가지로 나눌 수 있다!
1. dictionary로 그래프 구현하기
2. 생성된 정점을 찾기
3. 각 그래프들의 차이점 찾기

dictionary로 그래프와 간선을 구현하여 나타낼 수 있다면 문제를 풀기위한 기본을 준비한 것이다.

이제 생성된 정점을 찾을 것이다.
생성된 정점을 찾는 방법은 다음과 같다.

1. 간선들 중 보내기만 하는 정점들을 구한다.
2. 그렇게 나온 후보들 중 막대 그래프의 시작점에 해당하는 정점을 제거한다.
   (막대 그래프의 시작점의 정점은 1개의 간선만을 보낸다. 이를 이용해 제거할 수 있다.)
   (문제 제한사항: 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다. 따라서 생성된 정점이 보내는 간선은 최소 2개임을 알 수 있다.)
3. 남은 하나의 정점이 생성된 정점이다.

생성된 정점을 찾았다면 이제 생성된 정점에서 각 그래프의 노드로 이어졌기에 각 그래프의 임의의 노드를 알 수 있다.
그래프의 임의의 노드를 알았으니 이를 간선에 따라서 진행해본다.
이때, 막대 그래프는 간선의 마지막에 도달할 경우에, 더 이상 간선이 없게 된다.
그에 반면 8자 그래프는 끝도 없이 순환하지만, 중간에 2개의 간선을 가지고 있는 노드를 만나게 된다.
마지막으로 도넛그래프는 위와 같은 특징없이 끝없이 순환한다.

나는 이 특징들에 주목해 문제를 풀었다.

문제 해결

dictionary로 그래프 구현하기

for edge in edges:
        if max_val < max(edge):
            max_val = max(edge)
        if edge[1] not in dic:
            dic[edge[1]] = []
        if edge[0] not in dic:
            dic[edge[0]] = [edge[1]]
        else:
            dic[edge[0]].append(edge[1])

생성된 정점을 찾기

방문처리를 통해서 간선의 도착점에 해당하는 노드들을 제거해주고, 노드가 가지는 간선의 개수가 1개 이하인 노드를 제거해주었다.
구한 생성된 정점을 created_node 변수에 넣어 저장한다.

    visited = [0 for i in range(max_val+1)]
    for i in dic.values():
        for j in i:
            visited[j] = 1
    for i in dic:
        if len(dic[i]) <= 1:
            visited[i] = 1
    for i, val in enumerate(visited):
        if i!=0 and val == 0:
            created_node = i

각 그래프들의 차이점 찾기

순환시에 발생하는 각 그래프들의 간선 개수의 차이를 이용하여 그래프를 구별해주었다.

# 막대의 특징
    # 마지막에 어디로도 가지 않음
    # 도넛의 특징
    # 순환하여 결국 1로 돌아옴
    # 팔자의 특징
    # 순환하여 결국 1로 돌아옴 2개의 간선이 나가는 노드가 있음
    def dfs(val):
        start = val
        visited[start] = 1
        stack = [val]
        while stack:
            cur = stack.pop()
            
            if len(dic[cur])==0: # 막대 모양
                result[2] += 1
                return
            if len(dic[cur])==1:
                if visited[dic[cur][0]]==0:
                    stack.append(dic[cur][0])
                else:
                    result[1] += 1
                    return
            if len(dic[cur])==2:
                result[3] += 1
                return
    
    result[0] = created_node
    for i in dic[created_node]:
        dfs(i)

제출 코드

def solution(edges):
    answer = []
    dic = dict()
    max_val = 0
    for edge in edges:
        if max_val < max(edge):
            max_val = max(edge)
        if edge[1] not in dic:
            dic[edge[1]] = []
        if edge[0] not in dic:
            dic[edge[0]] = [edge[1]]
        else:
            dic[edge[0]].append(edge[1])
    visited = [0 for i in range(max_val+1)]
    
    for i in dic.values():
        for j in i:
            visited[j] = 1
    for i in dic:
        if len(dic[i]) <= 1:
            visited[i] = 1
    for i, val in enumerate(visited):
        if i!=0 and val == 0:
            created_node = i
    result = [0 for i in range(4)]
    visited = [0 for i in range(max_val+1)]
    # 막대의 특징
    # 마지막에 어디로도 가지 않음
    # 도넛의 특징
    # 순환하여 결국 1로 돌아옴
    # 팔자의 특징
    # 순환하여 결국 1로 돌아옴 2개의 간선이 나가는 노드가 있음
    def dfs(val):
        start = val
        visited[start] = 1
        stack = [val]
        while stack:
            cur = stack.pop()
            
            if len(dic[cur])==0: # 막대 모양
                result[2] += 1
                return
            if len(dic[cur])==1:
                if visited[dic[cur][0]]==0:
                    stack.append(dic[cur][0])
                else:
                    result[1] += 1
                    return
            if len(dic[cur])==2:
                result[3] += 1
                return
    
    result[0] = created_node
    for i in dic[created_node]:
        dfs(i)

    return result