[Swift 알고리즘] 프로그래머스(Lv.3) - 가장 먼 노드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 가장 먼 노드" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 가장 먼 노드

 

---

풀이

이번 문제는 그래프 문제입니다.

bfs를 시간 복잡도면에서 최적화를 시켜야 합니다.

 

1. 인접 리스트로 그래프 생성하기

그래프를 생성해줍니다.

그래프는 인접 행렬이 아닌 인접 리스트로 생성해야 합니다.

모든 노드를 탐색해야 하는 경우는 보통 인접 리스트가 훨씬 효율적입니다.

 

예를 들어, 3개의 노드에서 1번에서 2번 노드가 연결되었다고 해봅시다.

인접 행렬의 방식인 [false, true, false] 로 저장하는 것이 아니라, 1: [2] 로 저장해야 한다는 의미입니다.

인접 행렬은 모든 노드를 확인해야 하지만 인접 리스트는 연결된 노드 2만 꺼내 쓰면 되므로 1회만에 완료됩니다.

 

이번 문제는 노드가 최대 2만 개, 간선이 최대 5만 개 입력될 수 있습니다.

인접 행렬은 시간 복잡도가 O(V^2)이 되겠고 인접 리스트는 O(V + E)로 해결이 가능하겠죠?

 

따라서 이번 문제는 인접 행렬이 아닌 인접 그래프로 해결해야 시간 초과를 피할 수 있습니다.

 

2. BFS로 1번 노드와의 거리 구하기

BFS를 이용해 1번 노드와의 거리를 구합니다.

최단 거리를 구해야 하기 때문에 DFS가 아닌 BFS를 이용해야 합니다. (DFS는 최단 거리를 보장하지 않음)

 

BFS는 큐를 이용해야 합니다.

시간복잡도에 까다로운 문제이므로 removeFirst( )가 아닌 index 기법을 사용합니다.

1번에서 시작하여 연결된 모든 노드를 탐색합니다.

노드에 방문하면 최초 1회 누적 거리를 저장합니다. 

 

3. 최대값의 개수 구하기

최대값의 개수를 구합니다.

최대값을 구한 뒤 filter로 최대값만 남겨줍니다. 그 배열의 개수가 정답니다.

 

후기

전 원래부터 인접 행렬이 아닌 인접 그래프를 애용했기 때문에 그리 어렵지 않았습니다.

오히려 인접 행렬에 대해 더 알게 된 문제였습니다.

 

감사합니다!

---

전체 코드

import Foundation

func countDistance(_ graph: [Int: [Int]], n: Int) -> [Int] {
    var queue: [(Int, Int)] = [(1, 0)]
    var counts: [Int] = Array(repeating: -1, count: n+1)
    counts[1] = 0
    
    var index = 0
    while index < queue.count {
        let (node, count) = queue[index]
        index += 1
        
        for nextNode in graph[node]! {
            if counts[nextNode] > -1 {
                continue
            }
            
            counts[nextNode] = count + 1
            queue.append((nextNode, count+1))
        }
    }
    
    return counts
}

func solution(_ n:Int, _ edge:[[Int]]) -> Int {    
    var graph: [Int: [Int]] = [:]    
    for eg in edge {
        graph[eg[0], default: []].append(eg[1])
        graph[eg[1], default: []].append(eg[0])
    }
    // print("graph: \(graph)")
    
    let counts = countDistance(graph, n: n)
    // print("counts: \(counts)")
    
    let maxCount = counts.max()!
    let result = counts.filter { $0 == maxCount }.count
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.