스위프트 코딩테스트 강좌, 특정 거리의 도시 찾기

문제 설명

N개의 도시가 있으며, 이들 간에는 M개의 단방향 도로가 존재합니다.
각 도시는 1부터 N까지의 정수로 표현됩니다. 도시 A에서 도시 B로 가는
도로가 존재하면 A에서 B로 이동할 수 있습니다.
K라는 특정 거리가 주어질 때, 거리 K만큼 떨어져 있는 도시들을 모두 찾는
프로그램을 작성하세요. 동일한 도시가 두 번 이상 출력되지 않도록 합니다.

입력 형식

    N M K
    A1 B1
    A2 B2
    ...
    Am Bm

N: 도시의 개수 (1 ≤ N ≤ 30000)
M: 도로의 개수 (1 ≤ M ≤ 200000)
K: 찾고자 하는 거리 (0 ≤ K ≤ 30000)
A1, B1: 도시 A에서 도시 B로 가는 도로

출력 형식

    K 거리만큼 떨어져 있는 도시 번호를 오름차순으로 출력한다. 
    만약 그런 도시가 없다면 -1을 출력한다.

예시

입력

출력

문제 풀이 접근법

이 문제는 그래프 탐색(특히 너비 우선 탐색 BFS)을 활용하여 해결할 수 있습니다.
주어진 도시는 노드, 도로는 간선으로 모델링할 수 있으며, 특정 거리를
찾기 위해 BFS를 수행하여 거리 K에 도달하는 도시를 찾습니다.

BFS 알고리즘 개요

BFS는 시작 노드에서부터 인접한 모든 노드를 탐색하고, 탐색이 완료된 후
다음 레벨의 노드를 탐색하는 방식으로 작동합니다. 이 방식은 최단 경로
문제에 적합합니다.

구현 상세

다음은 스위프트로 BFS를 통해 특정 거리의 도시를 찾는 코드입니다.


    import Foundation

    struct City {
        var number: Int
        var distance: Int
    }

    func findCitiesAtDistanceN(n: Int, roads: [(Int, Int)], k: Int) -> [Int] {
        // 인접 리스트 생성
        var graph = [[Int]](repeating: [Int](), count: n + 1)
        for road in roads {
            let a = road.0
            let b = road.1
            graph[a].append(b)
        }

        // BFS 초기화
        var queue = [City]()
        var distances = Array(repeating: -1, count: n + 1)
        distances[1] = 0 // 시작 도시는 1로 가정
        queue.append(City(number: 1, distance: 0))

        while !queue.isEmpty {
            let current = queue.removeFirst()
            let currentDistance = current.distance
            for neighbor in graph[current.number] {
                if distances[neighbor] == -1 { // 아직 방문하지 않았다면
                    distances[neighbor] = currentDistance + 1
                    queue.append(City(number: neighbor, distance: distances[neighbor]!))
                }
            }
        }

        // K 거리의 도시 찾기
        let result = distances.enumerated().compactMap { index, distance in
            distance == k ? index : nil
        }.sorted()

        return result.isEmpty ? [-1] : result
    }

    // 예시 입력
    let roads = [(1, 2), (1, 3), (2, 4), (3, 4)]
    let result = findCitiesAtDistanceN(n: 4, roads: roads, k: 2)
    
    print(result) // Output: [4]

코드 설명

위 코드에서 먼저 인접 리스트를 생성합니다.
각 도시는 연결된 다른 도시들을 배열 형태로 저장합니다.
그 다음 BFS를 수행하여 각 도시에 대한 거리를 계산합니다.
마지막으로 거리 K에 해당하는 도시를 찾아 출력합니다.

복잡도 분석

그래프의 모든 노드를 방문하기 때문에
시간 복잡도는 O(N + M)입니다.
공간 복잡도 또한 O(N + M)입니다.

결론

이번 강좌에서는 특정 거리의 도시를 찾는 문제를 다뤄보았습니다.
BFS를 통해 효율적으로 해결할 수 있으며,
주의 깊은 구현이 필요합니다. 다양한 상황에서 활용할 수 있는
이 알고리즘을 익히면, 복잡한 그래프와 도로 문제를 해결할 수 있는
좋은 토대가 될 것입니다.