[Swift / Python] 프로그래머스(Lv3) - 가장 먼 노드

안녕하세요 !

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

풀이

이 문제는 기본적으로 최단거리 경로를 구하는 문제이기 때문에 BFS로 구현합니다.
양방향 그래프(graph), 노드를 방문했는지 체크하는 배열(check), 최대거리를 저장할 변수(maxDist), 그리고 우리가 구할 답을 저장할 변수(answer)를 만듭니다.

1. 첫번째 노드부터 시작한다고 문제에 되어있으니 첫번째 노드와 현재거리 0을 큐에 넣어줍니다 !
2. 큐에서 빼낸 거리가 maxDist보다 크다면 maxDist에 해당 거리값을 저장합니다.
   => maxDist보다 크다면 새로운 최대거리값을 만든거잖아요?
   그래서 answer를 0으로 만들어줍니다 !
3. 다음 노드들을 돌면서 방문하지 않은 곳이라면 큐에 넣어줍니다.

swift 코드입니다.

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph :[Int: [Int]] = [:]
    
    for route in edge {
        let a = route[0]
        let b = route[1]
        if !graph.keys.contains(a) {
            graph[a] = []
        }
        
        if !graph.keys.contains(b) {
            graph[b] = []
        }
        graph[a]!.append(b)
        graph[b]!.append(a)
    }
    
    var check = [Bool](repeating: false, count: n + 1)
    check[0] = true
    check[1] = true
    
    var maxDist = -1
    var answer = 0
    
    var q = [(node: Int, dist: Int)]()
    q.append((1, 0))
    
    while !q.isEmpty {
        let route = q.removeFirst()
        if route.dist > maxDist {
            maxDist = route.dist
            answer = 0 // 새로운 maxDist가 저장되었으니 answer를 0으로 초기화
        }
        answer += 1

        for next in graph[route.node]! {
            if !check[next] {
                check[next] = true
                q.append((next, route.dist + 1))
            }
        }
    }
    
    return answer
}

파이썬 코드입니다.

def solution(n, edge):
    graph = {}
    for item in edge:
        i, j = item
        if i not in graph:
            graph[i] = []
        if j not in graph:
            graph[j] = []

        graph[i].append(j)
        graph[j].append(i)

    q = []
    check = [False] * (n+1)
    q.append((1, 0))
    check[0] = True
    check[1] = True

    max_depth = -1
    ans = 0

    while q:
        x, depth = q.pop(0)
        if depth > max_depth:
            ans = 0
            max_depth = depth
        ans += 1

        for next_pos in graph[x]:
            if not check[next_pos]:
                check[next_pos] = True
                q.append((next_pos, depth+1))

    return ans