[Level 3 / bfs] 가장 먼 노드 + Swift

문제 링크

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

입력

let n = 6
let edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

출력

3

문제 풀이

이 문제는 bfs 알고리즘으로 푼다.

1. 연결 정보 저장하기

주어진 간선(edge) 배열을 통해 연결 dict를 만든다. 어느 노드에 어느 노드들이 연결되어 있는지를 저장한다.

let connections = [1: [3, 2], 2: [3, 1, 4, 5], 3: [6, 4, 2, 1], 4: [3, 2], 5: [2], 6: [3]]

구현한 코드는 다음과 같다.

var connections: [Int: [Int]] = [:]

func getConnections(_ key: Int, _ value: Int) {
    if connections[key] != nil {
        connections[key]?.append(value)
    } else {
        connections[key] = [value]
    }
}

for e in edge {
    getConnections(e[0], e[1])
    getConnections(e[1], e[0])
}

2. 변수 생성하기

방문 여부를 저장하는 visited 배열, 방문할 노드들을 저장하는 queue 배열, depth에 어떤 노드들이 있는지 저장하는 db 딕셔너리를 만든다.

큐에는 노드를 (노드 번호, depth) 형태로 저장한다.

db에는 [깊이: [해당 노드들]] 형태로 저장한다.

var visited: [Bool] = Array(repeating: false, count: n+1)
var queue: [(Int, Int)] = [] // (node, depth)
var db: [Int: [Int]] = [:]

3. bfs 함수

from은 시작 노드 번호이고 depth는 그래프 깊이값이다. 1에서 시작할 때를 생각해보자. from은 1이고 depth는 0이다.

1. connections에서 1과 연결된 노드 배열 [2, 3]을 찾는다.
2. 노드 배열에 대해서 for문을 돈다.
3. 이미 방문하였다면 for문을 넘긴다.
4. 방문하지 않았다면 방문했다고 저장한다.
5. db에 해당 깊이에 해당하는 value 배열에 노드를 추가한다.

let connections = [1: [3, 2], 2: [3, 1, 4, 5], 3: [6, 4, 2, 1], 4: [3, 2], 5: [2], 6: [3]]

func bfs(_ from: Int, _ depth: Int) {
    guard connections[from] != nil else { return }
    
    for node in connections[from]! {
        guard !visited[node] else { continue }
        
        visited[node] = true
        queue.append((node, depth))
        
        if db[depth] != nil {
            db[depth]?.append(node)
        } else {
            db[depth] = [node]
        }
    }
}

4. bfs 함수 실행

1. 먼저 1을 방문한다.
2. 방문했다고 저장한다.
3. queue가 비어있을 때까지 while문을 돈다.
4. 큐의 첫번째의 노드에 대해 bfs를 돈다.

queue.append((1, 0))
visited[0] = true
visited[1] = true
    
while !queue.isEmpty {
    let node = queue.removeFirst()
    bfs(node.0, node.1 + 1)
}

5. 멀리 떨어진 노드

1번 노드에서 가장 멀리 떨어진 노드를 찾는 것은, 가장 깊게 있는 노드들을 찾는 것과 마찬가지이다. 최대 깊이를 구한 다음에, 최대 깊이를 key로 갖는 value들의 갯수를 구해 반환한다.

let maxDepth = db.keys.max() ?? 1

return db[maxDepth]?.count ?? 1

전체 풀이

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var connections: [Int: [Int]] = [:]
    
    func getConnections(_ key: Int, _ value: Int) {
        if connections[key] != nil {
            connections[key]?.append(value)
        } else {
            connections[key] = [value]
        }
    }
    
    for e in edge {
        getConnections(e[0], e[1])
        getConnections(e[1], e[0])
    }

    var visited: [Bool] = Array(repeating: false, count: n+1)
    var queue: [(Int, Int)] = [] // (node, depth)
    var db: [Int: [Int]] = [:]
    
    func bfs(_ from: Int, _ depth: Int) {
        guard connections[from] != nil else { return }
        
        for node in connections[from]! {
            guard !visited[node] else { continue }
            
            visited[node] = true
            queue.append((node, depth))
            
            if db[depth] != nil {
                db[depth]?.append(node)
            } else {
                db[depth] = [node]
            }
        }
    }
    
    queue.append((1, 0))
    visited[0] = true
    visited[1] = true
    
    while !queue.isEmpty {
        let node = queue.removeFirst()
        bfs(node.0, node.1 + 1)
    }
    
    let maxDepth = db.keys.max() ?? 1

    return db[maxDepth]?.count ?? 1
}

참고

https://velog.io/@sainkr/프로그래머스-가장-먼-노드-Swift