[카카오 프로그래머스] 도넛과 막대

문제 이해하기

주어진 그래프에서 임의로 삽입된 노드를 찾고, 막대 그래프가 몇 개인지, 도넛 그래프, 8자 그래프가 몇 개인지 찾는 문제였다.여기서 중요한 점은 그래프를 순회해서 모양을 판별하는 것이 아니라, 노드와 간선의 개수를 가지고 어떤 그래프인지 판별하는 것이다.

 

문제 해결 방법 설명하기

1. 먼저 어떤 정점이 임의로 삽입된 정점은 진출차선만 있는 노드라고 생각했다.

2. 당연히 원래 있던 그래프에서 임의로 정접을 삽입했다고 했으니 해당 정점은 강제로 이어진 것 따라서 진출차선만 있어야 함 

3. 그 다음 dfs를 사용해서 그룹을 나눴고, 해당 그룹에는 몇 개의 노드와 엣지가 있는지 계산했다.

4. 모든 노드를 순회했다면, 그룹의 노드와 엣지 정보를 토대로 어떤 그래프가 있는지 판별했다.

코드

import sys
sys.setrecursionlimit(1000000)
def dfs(graph, start, visited_node, outdegree_vertex):
    visited_noge_num =  1
    visited_edge_num = outdegree_vertex[start]

    visited_node[start] = True

    for next in graph[start]:
        if not visited_node[next]:
            returned_visited_node, returned_visited_edge = dfs(graph, next, visited_node, outdegree_vertex)
            
            visited_noge_num += returned_visited_node
            visited_edge_num += returned_visited_edge
            
    return visited_noge_num, visited_edge_num

def search(graph, visited_node, disabled_node, indegree_vertex, outdegree_vertex):
    ans = [disabled_node, 0,0,0]
    
    group_num = 0
    group_dict = {}
    
    for node in graph[disabled_node]:
        indegree_vertex[node] -= 1
    
    visited_node[disabled_node] = True  
    
    for i in range(1, len(graph)):
        if not visited_node[i]:
            node_num, edge_num = dfs(graph, i, visited_node, outdegree_vertex)
            group_dict[group_num] = node_num, edge_num
            
            group_num += 1
            
    for group in group_dict:
        node, egde = group_dict[group]
        
        if node == egde:
            ans[1] += 1
        elif node == egde + 1: #직선모양
            ans[2] += 1
        elif node - 1 == egde - 2:
            ans[3] += 1
        
    return ans
            
            

def solution(edges):
    answer = []
    max_vertex = 0
    
    for edge in edges:
        max_vertex = max(max_vertex, edge[0], edge[1])
        
    visited = [True] * (max_vertex + 1)
    
    for edge in edges:
        visited[edge[0]] = False
        visited[edge[1]] = False
    
    outdegree_vertex = [0] * (max_vertex + 1)
    indegree_vertex = [0] * (max_vertex + 1)
    
    graph = [[] for _ in range(max_vertex + 1)]
    
    for edge in edges:
        indegree_vertex[edge[1]] += 1
        outdegree_vertex[edge[0]] += 1
          
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])

    for i in range(1, len(indegree_vertex)):
        if indegree_vertex[i] == 0 and 2 <= outdegree_vertex[i]:
            ans = search(graph, visited, i, indegree_vertex, outdegree_vertex)
            
            if ans:
                return ans
            
    return answer


if __name__ == "__main__":
    edges =[[1, 1], [2, 2], [4, 1], [4, 2]]
    
    print("ASD", solution(edges))

코드 리뷰

 

배운점 정리하기

처음에는 각 엣지를 방문 여부에 따라서 간선 정보와 노드 정보를 확인했다. 따라서 최대 방문 개수는 1,000,000 * 1,000,000이 되면서 시간초과에 걸렸다.

 

간선 정보를 한번만 방문해서 확인할 수 없을까를 했을 때 out_degree의 정보를 통해서 엣지가 아닌 정점의 방문을 통해서 최대 방문 개수를 1,000,000으로 줄일 수 있었다.

 

또한 기존의 순방향 그래프에서는 출발 순서가 중요했지만 양방향 그래프로 변경하면서 출발 순서의 제약을 없앨 수 있었다.

 

문제를 잘 읽고 판단하자