가장 먼 노드

문제풀이

효율성 실패

def graph(arrived, start, edge, n):
    while(len(arrived) < n):
        new_start= []
        for point in start:
            for root in edge[:]:
                if point in root:
                    root.remove(point)
                    list_root = list(root)
                    if not list_root[0] in arrived:          
                        new_start.append(list_root[0])
                        arrived.add(list_root[0])
                    edge.remove(root)
        start = new_start[:]
    return start
        
def solution(n, edge):
    answer = 0
    arrived = {1, }
    edge_set = [set(root) for root in edge]
    start = [1]
    last_edges = graph(arrived, start, edge_set, n)
    answer = len(last_edges)
    return answer

위의 코드는 내가 처음 시도해본 해법이다. 이 코드는 통과하지 못했는데 원인은 효율성에서 떨어졌다.

특히 경로를 찾는 for구문에서 비효율적인 탐색이 이루어졌다.

즉, 그래프 문제는 주어진 경로를 그대로 사용하는 것이 아니라 추가 작업을 한 뒤 쓸데없는 탐색을 최대한 줄여야 함을 배웠다.

효율성 해결

def graph(arrived, start, routes, n):
    while(len(arrived) < n):
        new_start= []
        for point in start:
            for route in routes[point]:
                if not route in arrived:          
                    new_start.append(route)
                    arrived.add(route)
        start = new_start[:]
    return start
        
def solution(n, edge):
    answer = 0
    arrived = {1, }
    routes = [set() for _ in range(n+1)]
    for route in edge:
        routes[route[0]].add(route[1])
        routes[route[1]].add(route[0])
    start = [1]
    last_edges = graph(arrived, start, routes, n)
    answer = len(last_edges)
    return answer

edge를 이용하여 그래프를 인접 리스트 형태로 만든 뒤 해결했다. 인접 행렬로 만들 경우 해당 노드가 다른 노드와 연결이 되었는지 다시 파악(순회) 해야 하기 때문에 역효과이다.

알고리즘

그래프

그래프를 표현하는데 2가지 경우가 있다. 바로 인접 리스트(adjacency list)와 인접 행렬(adjacent matrix)이다.

인접 리스트

각 노드에서 이웃 리스트에 접근할 수 있다. n개의 노드가 있을 때, 각 노드의 인접 리스트는 단순한 숫자 리스트다. 숫자로 노드에 접근 가능한 n개의 메인 리스트에 각 노드의 인접 리스트를 추가하면 된다.

 

알고리즘을 수행하는 작업이

이웃 노드를 반복해서 접근하는 경우 list를 사용하고,

그래프가 촘촘한 경우(간선이 많은 경우)에는 set을 사용하는 것이 좋다.

인접 행렬

각 노드의 모든 이웃에 대해 하나의 행을 갖는다. 각 행의 값은 1(True)과 0(False)으로 이루어진다.

중첩 리스트로 간단하게 구현할 수 있다.

행렬의 대각선 요소(동일한 노드)는 항상 0이다.

 

무향 그래프의 인접 행렬은 항상 대칭이다.

인접 행렬의 경우 가중치를 추가하려면, 1과 0 값을 가중치로 바꾸면 된다. 존재하지 않는 간선은 float('inf'), None, -1, 혹은 매우 큰 값 등으로 나타낸다.

 

인접 행렬에서 간선을 찾는 시간 복잡도는 O(1)이며, 어떤 노드의 이웃을 순회하는 시간 복잡 도는 O(n)이다.

in 연산자의 set, list 시간 복잡도

효율성 실패 코드에서 나는 list type인 edge의 원소와 지나간 포인트를 저장하는 arrived를 set type으로 변경하였다.

이를 통해 3가지 시간 초과 중 1가지는 통과할 수 있었다. 이를 통해 알 수 있었던 점은 in(not in) 구문은 list type보다 set type이 더 효율적임을 알 수 있었다.

시간 복잡도

• list, tuple
  Average: O(n)
  하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다.
• set, dictionary
  Average: O(1), Worst: O(n)
  내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간 복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.

출처

문제: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

인접 리스트(adjacency list): https://en.wikipedia.org/wiki/Adjacency_list

Adjacency list - Wikipedia

인접 행렬(adjacent matrix): https://en.wikipedia.org/wiki/Adjacency_matrix

Adjacency matrix - Wikipedia

list, set 시간 복잡도: https://twpower.github.io/120-python-in-operator-time-complexity

[Python] 파이썬 'in' 연산자 시간 복잡도(Time Complexity)

파이썬 자료구조와 알고리즘 - 미아 스타인 저/최길우 역