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

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

나의 풀이

1. 근접 노드를 구하자

1의 근접 노드는 2,3
2의 근접 노드는 1,4,5
3의 근접 노드는 1,4,6
4의 근접 노드는 2,3
5의 근접 노드는 2
6의 근접 노드는 3

var nearNode: [[Int]] = []

nearNode = Array(repeating: [], count: n+1)

edge.forEach{ 
        nearNode[$0[0]].append($0[1])
        nearNode[$0[1]].append($0[0])}

2. 방문한 노드를 체크하자

방문한 노드를 체크해야되는 이유는

• 재방문 금지 : 1 -> 2 -> 1
• 최단 경로만 허용 : 1 -> 3 -> 2 -> 5와 같이 1에서 5로 가는 최단경로(1 -> 2 -> 5) 가 아닌 경우를 방지하기 위해

var visited: [Bool] = []
visited = Array(repeating: false, count: n+1)

3. bfs로 탐색해보자

1. 1부터 시작해야 되니 result에 우선 1을 넣어준다.
2. 노드 1을 bfs 탐색한다.
   2-1. 노드 1의 인접 노드(2, 3)를 visited = true하여 방문 표시한다.
   2-3. result의 노드 2와 노드 3을 넣어준다.
3. 노드 2를 bfs 탐색한다.
   3-1. 노드 2의 인접 노드인 1이 visited = true 이기 때문에 방문하지 않는다.
   3-2. 노드 2의 인접 노드인 4가 visited = false 이기 때문에 방문 후(visited = true) result의 노드 4를 넣어준다.
   3-3. 노드 2의 인접 노드인 5가 visited = false 이기 때문에 방문 후(visited = true) result의 노드 5를 넣어준다.
4. 노드 3을 bfs 탐색한다.
   4-1. 노드 3의 인접 노드인 1이 visited = true 이기 때문에 방문하지 않는다.
   4-2. 노드 3의 인접 노드인 4가 visited = true 이기 때문에 방문하지 않는다.
   4-3. 노드 3의 인접 노드인 6가 visited = false 이기 때문에 방문 후(visited = true) result의 노드 6을 넣어준다.
   .
   .
   .

이런식으로 진행하다보면 제일 깊이 있는 노드의 갯수를 구할 수 있다.

var result: [Set<Int>] = [[1]] 

var depth = 1
visited[1] = true
while result.last!.count > 0{
   result.append([])
   for node in result[result.count - 2]{
        bfs(node, depth)
    }
     depth += 1
}
    
func bfs(_ s: Int,_ depth: Int){
    nearNode[s].forEach{
        if !visited[$0]{
            visited[$0] = true
            result[depth].insert($0)
        }
    }
}

전체 코드

import Foundation

var nearNode: [[Int]] = []
var visited: [Bool] = []
var result: [Set<Int>] = [[1]]

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    nearNode = Array(repeating: [], count: n+1)
    visited = Array(repeating: false, count: n+1)
    
    edge.forEach{
        nearNode[$0[0]].append($0[1])
        nearNode[$0[1]].append($0[0])}
    
    var depth = 1
    visited[1] = true
    while result.last!.count > 0{
        result.append([])
        for node in result[result.count - 2]{
            bfs(node, depth)
        }
        depth += 1
    }
    
    result.removeLast()
    
    return result.last?.count ?? 0
}

func bfs(_ s: Int,_ depth: Int){
    nearNode[s].forEach{
        if !visited[$0]{
            visited[$0] = true
            result[depth].insert($0)
        }
    }
}

2시간 고민하다 풀이 참고하고 다시 풀어보았다. 뭔가 풀릴것 같으면서도 시간초과로 절대 안풀리는 문제 .. 😭