[Swift 알고리즘] 백준 1697 숨바꼭질

안녕하세요 코코종입니다.

오늘은 bfs 문제를 이어서 풀어보겠습니다!

여담으로 swift는 queue가 없어서 상당히 킹받네요... array로 하자니 O(N)으로 remove를 해줘야하고... 참내....

모래주머니 훈련법도 아니고 ^^..

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/23.
//

import Foundation
// 백준 1697 숨바꼭질 BFS 실1

let input = readLine()!.split(separator: " ").map { Int(String($0)) ?? 0 }
let n = input[0]
let k = input[1]
let max = Int(1e5) + 1

var visit: [Bool] = Array(repeating: false, count: max) // 넉넉히 10만으로 처리? -> k보다 큰 점에서 뒤로 올수도 있음
var queue: [Int] = []
var depth: [Int] = Array(repeating: 0, count: max)
var answer = -1

queue.append(n)
visit[n] = true
while !queue.isEmpty {
    let q = queue.removeFirst()
    if q == k {
        answer = depth[k]
        break
    }
    
    if q+1 < max, !visit[q+1] {
        queue.append(q+1)
        depth[q+1] = depth[q] + 1
        visit[q+1] = true
    }
    
    if q-1 >= 0, !visit[q-1] {
        queue.append(q-1)
        depth[q-1] = depth[q] + 1
        visit[q-1] = true
    }
    
    if q*2 < max, !visit[q*2] {
        queue.append(q*2)
        depth[q*2] = depth[q] + 1
        visit[q*2] = true
    }
}

print(answer)

bfs친구랑 오래간만이라... queue에 넣지않고 dfs처럼 풀다가 틀렸지 뭐에요 ^^,,, 난 바보야...

그리고 k에서부터 또 오면서 2의 배수라면 일단! 반으로 쪼개고 아니라면 +- 1을 해주는 식으로 했는데 이건 생각해보니 무조건 반으로 가는게 잘못된거네요. 예를들어 15 16으로 주어진다고 반으로 쪼개서 8로 가버리면 대참사...(돌아갈수가 없어...) ㅎ.. 다음에는 조금만 더 생각을 잘 하는거로!

 

아이디어는 단순하게 +1, -1, *2를 해주면서 가는겁니다. 또한 실수했던 부분중에 하나가 visit처리를 처음에 q에만 해주는 식으로 구현했는데 생각해보니 3가지를 다 방문할때 depth가 똑같이 1씩 올라가야 하는데 방문한 인덱스만 depth를 올렸더니 5에서 [4, 6, 10]에 방문한다고 했을때 queue.first인 4만 방문한 처리가 되어서 6, 10은 방문하지 않은 인덱스가 되어 답이 꼬이게 됩니다(답이 6이 나오더라구요 ㅎ.. 디버깅 해보고 알았습니다.)

 

아.. 그리고 참고로 런타임 에러가 많이들 발생하셨을 텐데요 그 이유는 바로바로 범위에 있었답니다 하...

주어진 문제에서 0~10만으로 한다고 저도 실수도 10만으로 배열을 만들어버렸지 뭡니까(처음에는 10만 +1로 했는데 뭐에 홀렸는데 10만이 맞다고 생각해서 바꿨어요 ㅋㅋㅋㅋㅋ)

추가적으로 100001 을 Int(1e5)+1 으로 표현하는 방법도 있더라구요! 하나 배워갑니다~