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

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

프로그래머스

 

2023.07.17 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

기본적인 그래프 + BFS 풀이법으로 접근했습니다.

 

vetext 배열로 주어진 간선들을 이용해 그래프를 만들고 (이차원 배열)

1번 노드부터 시작해서 연결된 노드들을 순차적으로 큐에 넣습니다.

 

BFS를 활용하여 큐에서 노드들을 하나씩 빼서 해당 노드와 연결된 노드들을 다시 큐에 넣습니다.

큐에 넣으면서 1번 노드로부터의 거리를 기록해야 하기 때문에 distance 배열에 거리를 기록합니다.

거리는 이전 노드까지의 거리에 1을 더하는 방식입니다.

 

처음 문제를 풀고 제출했을 때 시간 초과가 발생했었는데 원인은 그래프를 이차원 배열로 만들 때 각 노드와 연결된 노드들을 저장할 때 연결되지 않는 노드들까지 배열에 포함시켰기 때문입니다.

var graph = Array(repeating: Array(repeating: false, count: n+1), count: n+1)
    
for vertex in edge {
    graph[vertex[0]][vertex[1]] = true
    graph[vertex[1]][vertex[0]] = true
}

이렇게 Bool 값을 가지는 2차원 배열로 놓고 그래프를 만들면 문제 조건에 따라 노드의 개수가 최대 20,000개이기 때문에 쓸모 없는 빈칸들이 많이 생성되게 됩니다.

예를 들어, 만약 노드 3번이 1개의 노드랑만 연결되어 있다면 graph[3]에는 19,999개의 false가 들어가게 됩니다.

 

BFS를 할 때 이 그래프를 반복문으로 돌게 되는데 이 때 19,999번이 추가되어 의미 없는 코드가 계속 실행되기 때문에 시간초과가 발생하는 것입니다..!

 

우리는 서로 연결된! 노드들만 필요하기 때문에 그래프를 저장하는 방식을 다음과 같이 수정하여 시간 초과를 해결했습니다.

var graph = Array(repeating: [Int](), count: n+1)
    
for vertex in edge {
    graph[vertex[0]].append(vertex[1])
    graph[vertex[1]].append(vertex[0])
}

그래프가 Bool 값이 아니라 Int를 가지게 했습니다.

즉, graph[i]에는 i번 노드와 연결된 노드 번호들이 곧바로 배열로 들어가게 됩니다.

이렇게 하면 굳이 연결되지 않은 노드에 대한 정보를 저장하지 않기 때문에 추후 반복문을 사용할 때 효율성이 훨씬 높아집니다.

 

풀이

fileprivate func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph = Array(repeating: [Int](), count: n+1)
    
    for vertex in edge {
        graph[vertex[0]].append(vertex[1])
        graph[vertex[1]].append(vertex[0])
    }
    
    var distance = Array(repeating: -1, count: n+1)
    
    var queue = [Int]()
    
    distance[1] = 0
    
    // 1번 노드와 연결된 노드들을 큐에 넣는다.
    for i in graph[1] {
        distance[i] = 1
        queue.append(i)
    }
    
    // BFS
    while !queue.isEmpty {
        let first = queue.removeFirst()
        
        for i in graph[first] {
            if distance[i] == -1 {
                distance[i] = distance[first] + 1
                queue.append(i)
            }
        }
    }
    
    // 1번 노드로부터 가장 멀리 떨어지 노드까지의 거리
    let farthestDistance = distance.max()!
    
    return distance.filter { $0 == farthestDistance }.count
}

distance 배열은 처음에 -1로 설정하고 BFS에서 탐색을 할 때 -1이 아닌 노드에 대해서는 이미 방문한 노드이기 때문에 큐에 넣지 않고 넘어가도록 했습니다.

 

BFS로 탐색을 마치면 distance 배열에는 1번노드로부터 각 노드들까지의 거리가 저장되게 됩니다.

따라서 distance.max()를 하면 최대 거리가 도출됩니다.

 

우리는 이 최대거리에 속한 노드의 개수가 필요하기 때문에 distance에 filter를 해서 최대 거리에 속하는 노드를 찾고 count로 개수를 구했습니다.

 

 

마무리

그래프와 BFS를 활용한 대중적인 문제였던 것 같습니다!

 

처음에 그래프를 만들 때 시간 복잡도를 고려하지 않아서 시간 초과가 발생했었는데 이 부분은 잘 기억하고 있다가 유사한 문제가 나왔을 때는 동일한 문제를 겪지 않도록 해야겠습니다!!