가장 먼 노드
문제 설명
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한사항
노드의 개수 n은 2 이상 20,000 이하입니다.
간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
BFS(너비 우선 탐색)란
BFS는 그래프 탐색 알고리즘 중 하나로, 넓이 우선 탐색이라고도 불린다. BFS의 기본 아이디어는 주어진 그래프에서 시작 노드를 기준으로 인접한 노드들을 먼저 탐색하고, 그 다음에 그 노드들과 연결된 노드들을 차례대로 탐색하는 방식이다.
BFS의 핵심은 큐(Queue) 자료구조를 사용하여 탐색을 진행하는 것이다. 큐는 FIFO(First In, First Out) 방식으로 동작하므로, 먼저 큐에 들어간 노드부터 탐색한다. 이 방식을 통해 BFS는 각 노드를 최단 거리로 탐색할 수 있다.
BFS 알고리즘 흐름:
- 시작 노드를 큐에 넣고 탐색을 시작합니다.
- 큐에서 노드를 하나씩 꺼내서, 그 노드와 연결된 모든 인접 노드를 큐에 넣습니다.
- 큐에 있는 노드를 모두 탐색할 때까지 이 과정을 반복합니다.
BFS는 각 노드를 한 번씩만 방문하고, 모든 노드를 탐색하며 최단 경로를 보장합니다. 따라서 BFS는 최단 거리를 구할 때 유용한 알고리즘이다.
최초 접근 방식 (removeFirst() 사용)
BFS를 이용하여 이 문제를 풀기 위해, 1번 노드에서부터 탐색을 시작한다. 각 노드까지의 최단 거리를 구하고, 가장 멀리 떨어진 노드의 개수를 찾는 방식이다. 하지만 이 방식에서는 큐에서 첫 번째 요소를 제거하는 removeFirst()를 사용하고 있는데, 이 방법은 큐에서 요소를 제거하는 데 시간이 O(n)이 걸리기 때문에 시간 초과 문제가 발생할 수 있다.
import Foundation
func solution(_ n: Int, _ edge: [[Int]]) -> Int {
var graph: [Int: [Int]] = [:]
for e in edge {
graph[e[0], default: []].append(e[1])
graph[e[1], default: []].append(e[0])
}
var distances = Array(repeating: -1, count: n + 1)
var queue = [1] // 1번 노드를 큐에 넣음
distances[1] = 0 // 1번 노드부터 시작하므로 거리 0으로 설정
while !queue.isEmpty {
let node = queue.removeFirst() // 큐에서 첫 번째 요소를 제거
for neighbor in graph[node, default: []] {
if distances[neighbor] == -1 { // 방문하지 않은 노드라면
distances[neighbor] = distances[node] + 1
queue.append(neighbor)
}
}
}
return distances.filter { $0 == distances.max() }.count
}위의 코드에서는 removeFirst()를 사용하여 큐에서 첫 번째 노드를 꺼내고, 그 노드와 연결된 인접 노드를 큐에 넣는 방식으로 BFS를 구현했다. 하지만 큐에서 요소를 제거하는 removeFirst()가 비효율적이기 때문에, 입력 크기가 커지면 시간 초과 문제가 발생할 수 있다.
최적화된 접근 방식 (큐의 앞부분을 관리하는 인덱스 front 추가)
시간 초과 문제를 해결하기 위해 큐의 앞부분을 관리하는 인덱스 front를 추가하여 성능을 개선할 수 있다. removeFirst()는 큐의 첫 번째 요소를 제거하는데 시간 복잡도가 O(n)이므로, 이를 front를 사용해 큐의 요소를 처리하는 방식으로 변경하면 O(1)로 큐를 관리할 수 있습니다.
import Foundation
func solution(_ n: Int, _ edge: [[Int]]) -> Int {
var graph: [Int: [Int]] = [:]
for e in edge {
graph[e[0], default: []].append(e[1])
graph[e[1], default: []].append(e[0])
}
var distances = Array(repeating: -1, count: n + 1)
var queue = [1] // 1번 노드를 큐에 넣음
distances[1] = 0 // 1번 노드부터 시작하므로 거리 0으로 설정
var front = 0 // 큐의 앞부분을 관리하는 인덱스
while front < queue.count {
let node = queue[front]
front += 1
for neighbor in graph[node, default: []] {
if distances[neighbor] == -1 { // 방문하지 않은 노드라면
distances[neighbor] = distances[node] + 1
queue.append(neighbor)
}
}
}
let maxDistance = distances.max() ?? 0
return distances.filter { $0 == maxDistance }.count
}