[프로그래머스] 가장 먼 노드 / 그래프, DFS, BFS / Python 코드

어제 오늘 푼 문제는 난이도 Lv.3의 가장 먼 노드이다. 문제 자체는 어렵지 않았지만 효율적인 풀이를 고민하는 데 노력이 들었다. 알고리즘 공부할 때 봤던 그래프의 개념과 문제 풀이 하면서 익혔던 DFS, BFS 개념 및 구현 방법을 복습할 수 있었던 좋은 문제였다. 

 

 

문제 설명

1부터 까지의 노드가 존재하는 그래프에서 1번 노드와 가장 먼 노드의 개수를 구하는 문제다. input으로 노드의 개수와 하나의 간선으로 연결된 두 노드의 배열이 list로 주어진다. 

 

 

문제 해결

이전에 DFS 문제를 많이 풀었기 때문에 자연스럽게 DFS로 풀어야겠다고 생각했는데 막상 코드를 짜고 보니 BFS 비슷한 방법으로 풀고 있었다. 지금 생각해보면 어떤 방법으로 풀어도 상관 없는 것 같다.

 

먼저 인접리스트로 만들어 놓고 

1번 노드부터 접근해 인접한 노드들을 차례로 방문하며

그 깊이에 있는 노드의 개수를 answer로 업데이트 시켜줬다.

 

 

풀이 코드 1

def solution(n, edge):
    answer = 0
    ad = [[] for i in range(n+1)]
    for i in edge:
        ad[i[0]].append(i[1])
        ad[i[1]].append(i[0])
    s = {1}
    visited = [1]
    while len(visited) < n:
        t = set()
        while s:
            node = s.pop()
            for i in ad[node]:
                if i not in visited:
                    visited.append(i)
                    t.add(i)
        answer = len(t)
        s = t.copy()
        print(s)
    
    return answer

제출해보니 마지막 두 개 tc에서 시간 초과로 실패했다.

그도 그럴 것이 loop는 세 개 중첩이요, 쓸모없는 집합을 하나 더 만들어서 copy하는 과정까지 있다.

 

친절한 프로그래머의 전현서님의 설명을 읽어 보니 answer와 visited의 두 역할을 다 할 수 있는 distance 배열을 통해서 낭비를 줄일 수 있었다.

인접 노드에 방문할 때 dist는 이전 노드의 dist +1이 되고

dist의 해당 인덱스가 0이 아니면 방문한 것과 동일한 의미이기 때문이다.

 

 

풀이 코드 2

from collections import deque

def solution(n, edge):
    ad = [[] for i in range(n+1)]
    for i in edge:
        ad[i[0]].append(i[1])
        ad[i[1]].append(i[0])

    dist = [0 for i in range(n+1)]
    dist[1] = 1
    
    q = deque()
    q.append(1)
    
    while (q):
        node = q.popleft()
        for i in ad[node]:
            if (dist[i] == 0):
                dist[i] = dist[node] + 1
                q.append(i)
    
    answer = dist.count(max(dist))
    
    return answer

어려운 분들에게 힌트는 dist 배열의 1번 인덱스를 1로 초기화시키는 것이다. 마지막에 dist-1을 하면 되겠다 싶은데 이 문제는 심지어 거리가 얼마나 되는지 묻지조차 않는다!

 

 

깔끔한 풀이를 하고 나면 이렇게 속이 다 시원할 수가 없다. 이후에 DFS, BFS 문제를 좀 더 풀어봐야겠다.