[프로그래머스]가장먼노드

문제설명

https://programmers.co.kr/learn/courses/30/lessons/49189

어렵지 않은 내용 이므로 패스

접근

적용할 수 있는 알고리즘

1. 다익스트라 알고리즘

   다익스트라 알고리즘은 일 대 다 알고리즘으로써 1번 노드에 대해 알고리즘을 적용했을 경우 1번 노드에서 최단거리로 갈 수 있는 모든 노드들을 구할 수 있다. 여기선 노드간 이동 횟수가 곧 거리이므로 모든 노드의 가중치를 1로 두어 구하면 된다.

   다 구하고 나서 최댓값의 갯수를 구하면 끝

2. BFS

   BFS에서 최단경로를 구할 때 que사이즈만큼 pop하는 과정이 있다. 최종적으로 기록된 size가 곧 마지막 노드들의 수이므로 이를 이용하자.

다익스트라에 비해 BFS가 구현하기 더 쉬우므로 BFS를 적용했다.

자료형 선택

문제에서 노드의 수가 최대 2만개, 엣지의 수가 최대 5만개로 주어졌다.

인접행렬이 속도가 빠르다 하여 인접행렬로 선언했다간 2만x2만 => 4억개가 필요하고 C언어 기준 int타입이라하면 16억byte가 요구된다.

따라서 인덱스가 출발노드, value가 도착 노드가 되도록 선언하였다.(해당 자료구조를 뭐라 불렀는지 잊었다)

구현

from queue import Queue

#인접행렬로 만들기엔 2만이므로 공간복잡도가 매우 큼. 2만x2만 -> 4백만.
def ConvertEdgeToGraph(edge):
    #1번 노드부터 시작, 최대 2만개. 그래프는 인덱스가 u,value가 v
    graph = [[] for _ in range(20001)]
    #양방향 그래프
    for u,v in edge:
        graph[u].append(v)
        graph[v].append(u)
    return graph

def solution(n, edge):

# BFS로 탐색하나, 최종 size 기록. 매 size만큼 pop해주는 과정 거치기.
    #초기화
    que = Queue()
    graph = ConvertEdgeToGraph(edge)
    visited = 1<<1
    que.put(1)

    #큐가 빌때까지 반복(마지막까지)
    while not que.empty():
        #사이즈 얻기
        size = que.qsize()
        #사이즈 만큼 pop하고 pop한 vertex에서 다음으로 이동한 것 que에 삽입
        for _ in range(size):
            u = que.get()
            for v in graph[u]:
                if not visited&(1<<v):
                    que.put(v)
                    visited = visited|(1<<v)

    answer = size
    return answer

코드를 글처럼!

전에 유튜브 영상을 보고 깨달은 내용을 바탕으로 최대한 코드로 이해하려고 노력했다.

• 영어를 해석할 때 영어->한국어변환->이해 에서 영어->이해로 줄이려는 노력
• 전에 교수님이 함수 내부를 구현하지 않고 미리 함수를 선언했던 것도 이런 차원이 아닐까 싶다.

따라서 이번엔 글로 쓰는 작업없이 코드에 필요 함수 및 주석을 달아놓고 구현했다.