프로그래머스: 가장 먼 노드

school.programmers.co.kr​

 

 

 

아이디어

1. 양방향 그래프이므로 각 노드와 연결된 모든 노드를 2차원 배열 형태로 정의

ex) [[],[2, 3], [1, 4, 5] ... ]

- 0번 노드는 없으니 비워둠

- 1번 노드와 연결된 노드는 2, 3

- 2번 노드와 연결된 노드는 1, 4, 5 (양방항 그래프이므로 1번 노드 포함)

 

2. 1번 노드와 떨어진 거리를 나타내는 배열 생성 (distance)

 

3. 큐를 생성하여 1번 노드와 연결된 노드를 큐에 넣어줌

- 큐에서 꺼내면서 꺼낸 노드와 연결된 노드를 큐에 넣어줌

- 큐에서 꺼냈으면 2. 에서 만든 거리를 나타내는 배열에 거리를 더해줘야 되는데

   이전 노드에 1만큼 떨어진 것이므로 튜플 형태로 큐에 넣어야 될듯 (이전 노드, 현재 노드)

- 거리를 나타내는 배열 distance에 ' distance[현재 노드] = distance[이전 노드] + 1' - 이미 거리가 정해진 노드는 재방문할 필요 없으므로 visited 처리

 

4. 가장 큰 값 개수 구하기

 

첫 번째 방법

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph = [[Int]](repeating: [Int](), count: n + 1) // 0번째 인덱스 제외하기 위해 n + 1개 생성
    var distance = Array(repeating: 0, count: n + 1)      // 1번 노드부터 떨어진 거리
    var visited = Array(repeating: false, count: n + 1)   // 방문 처리
    
    edge.forEach {
        graph[$0[0]].append($0[1])
        graph[$0[1]].append($0[0])
    }

    var queue = graph[1].map{(1, $0)} // 1번 노드와 연결된 노드 삽입 (이전 노드, 현재 노드) 튜플 형태
    visited[1] = true
    graph[1].forEach {visited[$0] = true}
    
    while !queue.isEmpty {
        let (prevNode, currentNode) = queue.removeFirst() 
        distance[currentNode] = distance[prevNode] + 1
        
        for next in graph[currentNode] {
            if visited[next] { continue }
            queue.append((currentNode, next))
            visited[next] = true
        }
    }
    let maxDistance = distance.max() ?? 0
    return distance.filter {maxDistance == $0}.count
}

 

1번 노드와 연결된 노드를 큐에 삽입하는 방식을 map을 이용하여 큐를 초기화하고

다시 forEach로 visited를 방문 처리했다

그러나, graph[1]을 두 번 순회하므로 한 번에 처리하면 속도가 개선될 거 같았다

 

두 번째 방법

큐를 초기화 할 때  forEach문 내부에 큐에 데이터 삽입과 visited 처리를 함께 처리

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph = [[Int]](repeating: [Int](), count: n + 1) // 0번째 인덱스 제외하기 위해 n + 1개 생성
    var distance = Array(repeating: 0, count: n + 1)      // 1번 노드부터 떨어진 거리
    var visited = Array(repeating: false, count: n + 1)   // 방문 처리
    
    edge.forEach { // 1. 양방향 그래프이므로 각 노드와 연결된 모든 노드를 2차원 배열 형태로 정의
        graph[$0[0]].append($0[1])
        graph[$0[1]].append($0[0])
    }

    var queue = [(Int, Int)]()  // (이전 노드, 현재 노드) 튜플 배열
    graph[1].forEach {
        queue.append((1, $0)) // 1번 노드와 연결된 노드 삽입 (이전 노드, 현재 노드) 튜플 형태
        visited[$0] = true    // queue에 넣은 노드는 방문 처리
    }
    visited[1] = true
    
    while !queue.isEmpty { // 3.
        let (prevNode, currentNode) = queue.removeFirst() 
        distance[currentNode] = distance[prevNode] + 1 // 이전 노드보다 거리가 1만큼 떨어짐
        
        for next in graph[currentNode] {
            if visited[next] { continue } // 이미 방문했으면 continue
            queue.append((currentNode, next)) // (이전 노드, 현재 노드) 튜플 형태
            visited[next] = true // 큐에 들어갔으므로, 동일한 노드를 큐에 다시 넣지 않기 위해 방문 처리
        }
    }
    let maxDistance = distance.max() ?? 0
    return distance.filter {maxDistance == $0}.count
}

 

 

 

 forEach문 내부에 큐에 데이터 삽입과 visited 처리를 함께 처리 었는데 오히려 속도가 더 느려졌다?!

두 코드의 차이 분석

첫 번째 코드

var queue = graph[1].map { (1, $0) } // O(n)
visited[1] = true
graph[1].forEach { visited[$0] = true } // O(n)

• graph[1]에 연결된 노드를 한 번에 map을 사용해 (이전 노드, 다음 노드) 형태로 배열 생성 (O(n))
• graph[1].forEach { visited[$0] = true } → 방문 처리를 한 번에 수행 O(n))

→ 총 연산 횟수: O(n) + O(n) = 2O(n) = O(n)

두 번째 코드

var queue = [(Int, Int)]()
graph[1].forEach {
    queue.append((1, $0))  // O(1) * n
    visited[$0] = true      // O(1) * n
}
visited[1] = true

• forEach 내부에서 graph[1]의 모든 노드를 하나씩 큐에 추가 및 방문 처리

→ 총 연산 횟수: O(n) + O(n) = 2O(n) = O(n)

 

 

시간 복잡도는 동일하지만, 첫 번재 코드가 더 빠른 이유는 map과 append의 메모리 할당 방식의 차이이다

map은 내부적으로 한 번에 새로운 배열을 만들고

append는 요소를 하나씩 추가하면서 배열의 크기가 부족하면 메모리를 재할당하는 가능성이 있다

즉, map을 쓰면 불필요한 메모리 재할당이 줄어들고, 최적화된 방식으로 배열이 생성되므로 append 방식보다 더 빠를 가능성이 높아진다

데이터셋이 많을수록 메모리 재할당 가능성이 높아지기 때문에 map이 더 유리할 수 있다