문제 설명
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한 사항
-
노드의 개수 n은 2 이상 20,000 이하입니다.
-
간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
-
vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
입출력 예
| n | vertex | return |
|---|---|---|
| 6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] | 3 |
입출력 예 설명
예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.
내가 제출한 코드
import Foundation
class Node {
private let number: Int
private let dis: Int
init(_ number: Int, _ dis: Int) {
self.number = number
self.dis = dis
}
public func getNumber() -> Int {
return self.number
}
public func getDis() -> Int {
return self.dis
}
}
struct Queue<T> {
private var items = [T]()
public mutating func enqueue(_ item: T) {
items.append(item)
}
public mutating func dequeue() -> T? {
return (items.isEmpty) ? nil : items.removeFirst()
}
public func isEmpty() -> Bool {
return (items.isEmpty) ? true : false
}
}
func solution(_ n:Int, _ edge:[[Int]]) -> Int {
var visited: [Bool] = Array(repeating: false, count:n+1) // 중복 방지
let graph: [[Int]] = makeGrahph(edge, n) // [vertex: [edge]]
var queue = Queue<Node>()
var distantArray: [Int] = [] // 1번 노드에서 각 노드마다 거리 계산
queue.enqueue(Node(1,0)) // init Node(number,dis)
while !queue.isEmpty() { // queue가 빌때까지
let curNode = queue.dequeue()! // -> queue의 isEmpty체크 했으므로 foreced unwrapping used
let curNum = curNode.getNumber()
let curDis = curNode.getDis()
if !visited[curNum] {
visited[curNum] = true
distantArray.append(curDis)
let edgeList = graph[curNum]
for edge in edgeList {
queue.enqueue(Node(edge,curDis+1))
}
}
}
return calFarawayNode(distantArray)
}
// 양방향 그래프 만듬
func makeGrahph(_ vertex: [[Int]], _ n: Int) -> [[Int]] {
var graph: [[Int]] = Array(repeating: [], count:n+1)
for v in vertex {
graph[v[0]].append(v[1])
graph[v[1]].append(v[0])
}
return graph
}
// 제일 멀리 떨어진 노드의 수찾음
func calFarawayNode(_ distanceArray: [Int]) -> Int {
let max = distanceArray.max()!
return distanceArray.filter{$0==max}.count
}코드 설명
이번 문제는 그래프 문제이다. 그래프 문제는 주로 bfs, dfs 알고리즘을 사용한다. 그 중 노드1 에서 가장 먼 노드의 개수를 찾아야 하므로 BFS가 적합하다고 생각한다. 물론 DFS를 사용하여 문제를 해결하는 방법도 존재한다. 자세한 설명은 코드를 보면서 설명한다.
그러면 그래프에 사용되는 노드 클래스 Node를 설명한다.
class Node {
private let number: Int
private let dis: Int
init(_ number: Int, _ dis: Int) {
self.number = number
self.dis = dis
}
public func getNumber() -> Int {
return self.number
}
public func getDis() -> Int {
return self.dis
}
}Node 클래스는 노드가 해당하는 번호를 나타내는 number 프로퍼티와 1번 노드와의 거리를 나타내는 dis프로퍼티를 가진다. 이 클래스로 그래프의 노드를 표현한다.
다음으로 입력된 노드 연결 정보vertex를 가지고 그래프를 만드는 함수 makeGraph를 확인한다.
func makeGrahph(_ vertex: [[Int]], _ n: Int) -> [[Int]] {
var graph: [[Int]] = Array(repeating: [], count:n+1)
for v in vertex {
graph[v[0]].append(v[1])
graph[v[1]].append(v[0])
}
return graph
}이번 문제에서 그래프는 양방향 그래프다. 그러므로 노드들을 서로 연결해야 한다. 연결 방법은 2차원 배열을 사용한다. 예를 들어 grpah 프로퍼티가 [[0], [3,2], [4,5]]의 값을 가진다면 1번 노드는 3,2번 노드에 연결되어 있고 2번 노드는 4번, 5번 노드에 연결되어 있다는 의미가 된다. 즉 2차원 배열의 index는 노드 번호를 나타내고 인덱스에 해당하는 1차원 배열은 연결된 노드들(edge)를 나타낸다.
이제 그래프를 만들었으므로, BFS 방법을 사용하여 그래프를 탐색한다.
queue.enqueue(Node(1,0)) // init Node(number,dis)
while !queue.isEmpty() { // queue가 빌때까지
let curNode = queue.dequeue()! // -> queue의 isEmpty체크 했으므로 foreced unwrapping used
let curNum = curNode.getNumber()
let curDis = curNode.getDis()
if !visited[curNum] {
visited[curNum] = true
distantArray.append(curDis)
let edgeList = graph[curNum]
for edge in edgeList {
queue.enqueue(Node(edge,curDis+1))
}
}
} 그래프 탐색은 1번 노드부터 시작한다. 그러므로 큐에 초깃값으로 1번 노드의 정보를 나타내는 Node 클래스 인스턴스를 생성하여 반입한다. 이제 큐가 빌 때까지 반입과 반출을 반복한다. 우선 큐에서 반출한 노드를 curNode라고 한다.
큐에서 반출한 노드의 번호(curNum)이 visited배열에서 false값을 가진다면 탐색하지 않는 노드이므로 해당 노드와 연결된 노드들을 찾아야 한다. 찾는 방법은 우리가 이전에 생성하였던 2차원 배열 graph 프로퍼티에 인덱스의 값을 찾으면 된다. 이제 연결된 노드들을 찾았으므로 각 노드마다 해당하는 Node 클래스의 인스턴스를 생성하여 큐에 반입한다.
이때 우리는 1번 노드와 제일 멀리 떨어진 노드들의 수를 알아야 하므로 노드를 탐색할 때마다 1번 노드와 해당 노드의 사이의 거리(curDis)를 distantArray 배열에 추가한다. 이 배열에서 최댓값을 가지는 원소들이 1번 노드와 가장 멀리 떨어진 노드가 된다.
마지막으로 1번 노드와 가장 멀리 떨어진 노드의 수를 찾는 calFarawayNode 함수이다.
// 제일 멀리 떨어진 노드의 수찾음
func calFarawayNode(_ distanceArray: [Int]) -> Int {
let max = distanceArray.max()!
return distanceArray.filter{$0==max}.count
}1번 노드와 떨어진 거리를 나타내는 distanceArray 프로퍼티 배열에서 최댓값을 찾는다. 이는 max 메소드를 사용한다. 최댓값을 찾았다면 배열에서 최댓값을 가지는 수가 1번 노드와 가장 멀리 떨어진 노드의 수이다. 이는 filter 메소드를 사용하여 수를 찾고 이를 반환한다. 그러면 우리가 원하는 결론을 얻을 수 있다.
몰랐던 사실 or 기억하면 도움이 될 만한 사실
Swift에서 그래프 생성방법
나는 이전까지 그래프의 연결을 딕셔너리로 표현하였다. 노드의 번호를 딕셔너리의 key로 표현하고 연결된 edge들을 value로 표현하였다. 물론 이때 value는 리스트 형태이다. 그러나 이번 문제를 해결하면서 2차원 배열로 그래프를 표현하는 방법을 알게 되었다. 아래에 2가지 방법으로 그래프를 생성하는 코드를 기술한다.
2차원 배열로 생성
func makeGrahph(_ vertex: [[Int]], _ n: Int) -> [[Int]] {
var graph: [[Int]] = Array(repeating: [], count:n+1)
for v in vertex {
graph[v[0]].append(v[1])
graph[v[1]].append(v[0])
}
return graph
}딕셔너리로 그래프 생성
func makeGrahph(_ vertex: [[Int]]) -> [Int:[Int]] {
var graph: [Int:[Int]] = [:]
for v in vertex {
if let edge = graph[v[0]] {
graph[v[0]] = edge + [v[1]]
} else {
graph[v[0]] = [v[1]]
}
if let edge = graph[v[1]] {
graph[v[1]] = edge + [v[0]]
} else {
graph[v[1]] = [v[0]]
}
}
return graph
}2차원 배열 말고 딕셔너리를 이용하면 옵셔널 타입을 다뤄야 하기 때문에 코드의 복잡성이 더 증가하는 것을 확인할 수 있다. 두 방법 모두 edge를 인덱스와 서브스크립트로 접근하기 때문에 시간적인 측면에서도 동일하다고 생각한다.(주관적인 생각)
그러므로 2차원 배열이 그래프를 만드는 측면에서 더 쉽게 접근할 수 있다고 생각한다. 물론 그래프가 가중치를 포함하면 위와 같이 간단하지 않겠지만, 가중치를 첫 번째 원소에 고정시키는 방법을 사용한다면 배열로도 구현할 수 있다.
그러므로 두 방법 중 본인에게 편한 방법을 사용하자.
