Swift) 백준 1697번 숨바꼭질 - S1

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

 

문제 풀이

bfs로 최단 경로를 탐색하는 방식으로 풀이. 각 점마다 +1, -1, *2씩 해주므로 한번 방문한 점은 다시 방문할 필요가 없으므로 방문처리를 하여 문제를 해결. 

import Foundation

struct Node {
    let count: Int
    let location: Int
}

let nk = readLine()!.split(separator: " ").map{ Int($0)! }
var visited = Array(repeating: false, count: 100001)

func solution() {
    var queue: [Node] = [.init(count: 0, location: nk[0])]
    if nk[0] == nk[1] {
        print(0)
        return
    }
    
    while !queue.isEmpty {
        let popNode = queue.removeFirst()
        for i in [-1, 1, popNode.location] {
            let nx = popNode.location+i
            if nx >= 0 && nx <= 100000 && !visited[nx] {
                if nx == nk[1] {
                    print(popNode.count+1)
                    return
                } else {
                    visited[nx] = true
                    queue.append(.init(count: popNode.count+1, location: nx))
                }
            }
        }
    }
    
}

solution()