[Swift 백준] 18352 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

 

풀이 아이디어

- 단방향 그래프를 이용한 bfs문제입니다.

- 출발점에서 목표치까지 거리를 쟀을 때 특정 거리인 도시를 모두 출력합니다

- 해당 문제는 수의 범위가 크므로 큐를 직접 작성하여 풀이합니다.

풀이 

import Foundation

// n 도시개수, m 도로개수, k 목표거리, x 출발번호
let nmkx = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m, k, x) = (nmkx[0], nmkx[1], nmkx[2], nmkx[3])

var graph: [[Int]] = Array(repeating: [], count: n + 1)

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (input[0], input[1])
    graph[a].append(b) // 단방향이므로 b -> a는 추가하지 않음
}

// 거리 저장 배열 (-1로 초기화)
var distance = Array(repeating: -1, count: n + 1)

func bfs(start: Int) {
    var q = Q()
    q.enqueue(start)
    distance[start] = 0  // 시작 지점은 거리 0

    while !q.isEmpty {
        let current = q.dequeue()
        
        for next in graph[current] {
            if distance[next] == -1 {  // 방문하지 않은 노드라면
                distance[next] = distance[current] + 1
                q.enqueue(next)
            }
        }
    }
}

bfs(start: x)

var resultArr = [Int]()
for i in 1...n {
    if distance[i] == k {
        resultArr.append(i)
    }
}

// 결과 출력
if resultArr.isEmpty {
    print("-1")
} else {
    resultArr.forEach { print($0) }
}


struct Q {
    private var input = [Int]()
    private var output = [Int]()
    var isEmpty: Bool { input.isEmpty && output.isEmpty }

    mutating func enqueue(_ newElement: Int) {
        input.append(newElement)
    }
    
    mutating func dequeue() -> Int{
        if output.isEmpty {
            output = input.reversed()
            input = []
        }
        return output.removeLast()
    }
}