[프로그래머스] lv3. 가장 먼 노드풀이 / Python, JavaScript

프로그래머스

 

lv3. 가장 먼 노드

접근한 방법

BFS를 이용해서 빠르게 해결할 수 있습니다. 주의할 점은 간선 저장 시 인접 행렬을 사용할 경우 시간이 초과됩니다. 노드 보다 간선이 적을 경우 매우 비효율적이므로 상대적으로 탐색에 더 효율적인 인접 리스트를 사용합니다.

 

간선을 저장했다면 큐를 이용해서 노드(now)와 간선 길이(cnt)를 관리합니다.

JavaScript에서는 별도의 큐 라이브러리가 없으므로 shift 메서드를 사용하고 문제에는 영향이 없지만 비효율적이라 싫다면 front를 가리키는 포인터를 설정하여 큐 처럼 사용하면 되겠습니다.

 

결과 배열(result)에 현재 방문한 노드까지의 간선 길이를 입력해주고 현재 방문한 노드에 연결된 리스트를 확인하여 방문하지 않은 노드를 탐색합니다. 최종적으로 결과 배열에는 노드1로부터 각 노드에 도달하는 길이가 저장되고 가장 긴 길이의 개수를 카운트하여 리턴합니다.

 

 

Python(인접 리스트)

def solution(n, edge):
    graph = [[] for _ in range(n + 1)]
    for _ in edge:
        a, b = _
        graph[a].append(b)
        graph[b].append(a)
    from collections import deque
    q = deque()
    q.append((1, -1))
    visited = [0] * (n + 1)
    visited[1] = 1
    
    result = [0] * (n + 1)
    while q:
        now, cnt = q.popleft()
        result[now] += cnt + 1
        for i in graph[now]:
            if not visited[i]:
                visited[i] = 1
                q.append((i, cnt + 1))
    return result.count(max(result))

Python(인접 행렬  / 시간 초과)

def solution(n, edge):
    graph = [[0] * (n + 1) for _ in range(n + 1)]
    for _ in edge:
        a, b = _
        graph[a][b] = 1
        graph[b][a] = 1
    
    from collections import deque
    q = deque()
    q.append((1, -1))
    visited = [0] * (n + 1)
    visited[1] = 1
    
    result = [0] * (n + 1)
    while q:
        now, cnt = q.popleft()
        result[now] += cnt + 1
        for i in range(len(graph[now])):
            if graph[now][i] and not visited[i]:
                visited[i] = 1
                q.append((i, cnt + 1))
    return result.count(max(result))

JavaScript

function solution(n, edge) {
    const graph = Array.from({length: n + 1}, () => [])
    edge.forEach(e => {
        const [a, b] = e
        graph[a].push(b)
        graph[b].push(a)
    })
    const q = [[1, -1]]
    const visited = Array(n + 1).fill(0)
    visited[1] = 1
    const result = Array(n + 1).fill(0)
    while (q.length) {
        const [now, cnt] = q.shift()
        result[now] += cnt + 1;
        for (const i of graph[now]) {
            if (!visited[i]) {
                visited[i] = 1
                q.push([i, cnt + 1])
            }
        }
    }
    const m = Math.max(...result)
    let cnt = 0
    result.forEach(v => {
        if (v === m) cnt += 1
    })
    return cnt
}