1697번: 숨바꼭질

문제 풀이 아이디어

# 사용해야 하는 알고리즘 = bfs
  : t초 후의 위치에서 앞으로 걷기 / 뒤로 걷기 / 순간이동 세가지 경우에 대해
  : 완전 탐색을 하여 최단 거리를 구하면 됩니다.

# 문제 풀이 아이디어
  : 방문 체크를 하기 위한 수직선을 만듭니다.
  : 수빈이가 이동하는 위치를 방문체크하면서 3가지 이동 케이스를 완전 탐색합니다.
  : 결국 동서남북 탐색과 동일한 원리로 하면 됩니다.

# 의사코드
  1. 입력을 받고 빈큐와 방문체크용 배열을 선언한다.
  2. 큐에 n과 t(= 0)을 구조체로 만들어서 넣고 bfs를 실시합니다.
      2-1. 큐에서 나온 위치가 k와 동일하면 t를 출력합니다.
      2-2. 큐에서 나온 위치에 +1 / -1 / *2가 미방문이면 큐에 넣습니다.

코드

// 숨바꼭질

// 현재 위치와 걸린 시간을 저장하는 구조체
struct Position {
    let n: Int
    let t: Int
    
    // 동생의 위치에 도착했는지 여부
    var isArrived: Bool {
        return n == K
    }
}

// 큐 구현
struct Queue {
    private var queue = [Position]()
    private var index = 0
    
    var isEmpty: Bool {
        return queue.count - index == 0
    }
    
    mutating func push(_ p: Position) {
        queue.append(p)
    }
    
    mutating func pop() -> Position {
        defer {
            index += 1
        }
        return queue[index]
    }
}

// 이동 방법 3가지 함수로 구현
func plusOne(_ n: Int) -> Int {
    return n + 1
}

func minusOne(_ n: Int) -> Int {
    return n - 1
}

func multiplyTwo(_ n: Int) -> Int {
    return n * 2
}

// 위 함수들을 배열에 저장 (반복문을 사용하기 위해서)
let moves :[(Int) -> Int] = [plusOne, minusOne, multiplyTwo]

// 현재 위치가 주어진 범위를 벗어난 것은 아닌지 알아보는 extension
extension Int {
    var isValid: Bool {
        return self >= 0 && self <= 100000
    }
}

// bfs 구현
func bfs() {
    // 큐와 방문체크 배열
    var queue = Queue()
    var check = Array(repeating: false, count: 100001)
    
    // 시작점 큐에 push
    queue.push(Position(n: N, t: 0))
    check[N] = true
    
    // 완전탐색 시작
    while !queue.isEmpty {
        let now = queue.pop()
        if now.isArrived { print(now.t); return } // 도착하면 출력하고 리턴
        
        // 3가지 이동 (앞으로 걷기, 뒤로 걷기, 순간이동)에 대해서 완전 탐색
        for i in 0..<3 {
            let next = moves[i](now.n) //👉 배열의 subscript로 접근한 함수 실행하는 방법
            if next.isValid && !check[next] {
                queue.push(Position(n: next, t: now.t + 1))
                check[next] = true
            }
        }
    }
}

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], K = input[1]

// bfs 실시
bfs()