[백준 스위프트] 1697번 숨박꼭질

아이디어

처음에 BFS 문제라 생각했다가 생각보다 조건이 간단하여 굳이 bfs로 안 풀어도 된다고 생각했다. 문제를 오독한 탓인데 수빈이의 동생이 수빈이보다 더 왼쪽 (K < N)일 가능성을 판단하지 못하고 생각보다 while로 푸는 것이 복잡하고 단계를 많이 거쳐야 했던 탓으로 생각한다.

 

오답

오답을 굳이 적어야 하나 싶었지만 머리속에서 5 17이라는 예시 조건에서 어떻게 문제를 풀어가는지를 생각했었다. 힌트에서 내가 생각한 것과 똑같은 방향으로 풀렸기 때문에 더욱 그렇게 착각한듯하다. 순간이동으로 단숨에 좁히는 것이 유리하므로 순간 이동하고 x-1, x+1 좌표에 동생이 있는지 확인하게 하였다. 아니면 K가 N의 2배 이상이 아닐 경우에만 순간 이동하고 아닌 경우에는 그냥 한 칸 N-1 하여 다시 순간이동을 시도하게 하였다. 결과로는 시간 초과가 떴다.

let input = readLine()!.split(separator: " ").map { Int(String($0))!}
var N = input[0]
let K = input[1]
var result = 0

while N != K {
    if K - 1 == (N * 2) {
        result += 2
        break
    }
    if K + 1 == (N * 2) {
        result += 2
        break
    }
    if K > (N * 2) {
        N *= 2
        result += 1
        continue
    }
    N -= 1
    result += 1
}
print(result)

 

해답

결국 실패하여 다시 bfs로 풀었다. 아직 bfs에 감을 못 잡아 검색하여 풀었다. 전형적인 bfs와 같이 큐에 좌표를 넣되 이미 큐에서 한번 방문했던 장소는 다시 큐에 넣어서 처리할 필요가 없다. 어차피 모든 경우를 탐색해가면서 너비 탐색하는 것이기 떄문이다.

이를 위해 check 배열로 계속 방문 여부를 판명하게 하였다. 여기서 count를 100000으로 설정하면 컴파일 에러가 뜨니까 조심해야 한다.

큐에는 이동 횟수와 좌표를 동시에 넣어서 편하게 처리하게 하였다. 배열 안에 (0, 0)식으로 한 번에 두 수를 집어넣을 수 있는 걸 아니까 너무 편한 듯하다.

let input = readLine()!.split(separator: " ").map { Int(String($0))!}
var N = input[0]
let K = input[1]
var check = [Bool](repeating: false, count: 100_001)
var q = [(N, 0)]
check[N] = true
func isValid(_ num: Int) -> Bool {
    if num < 0 || num > 100_000 || check[num] == true {
        return false
    }
    return true
}
while !q.isEmpty {
    let (x, cnt) = q.removeFirst()
    if x == K {
        print(cnt)
        break
    }
    if isValid(x - 1) {
        check[x - 1] = true
        q.append((x - 1, cnt + 1))
    }
    if isValid(x + 1) {
        check[x+1] = true
        q.append((x + 1, cnt + 1))
    }
    if isValid(x * 2) {
        check[x * 2] = true
        q.append((x * 2, cnt + 1))
    }
}

https://chanhuiseok.github.io/posts/baek-14/