[Swift] 백준1697번 숨바꼭질 문제풀이

이번엔 백준 1697번 문제 숨바꼭질을 풀어보겠습니다.

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

1697번: 숨바꼭질

BFS로 풀어야 한단것을 안다면 그렇게 어려운 문제 같진 않은데 정답 비율이 생각보다 낮네요.

일반적으로 BFS문제는 2차원 배열에서 최단거리를 찾는 문제가 많았습니다. 근데 이번 문제는 2차원 배열이 보이지 않아 BFS인지 잘 모를 수 있는데요!

2차원 배열에서 상 하 좌 우로 최단거리를 체크하듯이 여기서는 x-1 x+1 2*x를 방문하며 최단거리를 체크하면됩니다.

위에 보이는 수빈이의 위치가 5일때의 예제를 한 번 봅시다!

우선 방문 체크를 해야겠죠?? 모든 배열요소를 -1로 초기화한 0부터 100001까지의 배열을 만들어둡니다.

수빈이의 위치인 5는 시간상 0초가 걸리겠죠. Queue에 시작점 5를 넣어두고 방문배열에 0을 할당하여  5는 방문했음을 표시합니다.

그리고 큐가 빈큐가 될때까지 반복해봅시다. ( 방문배열[동생위치] == -1 동안 반복시키는 방법도 있습니다 )

Queue에서 5를 빼고 5에서 갈 수 있는 4 , 6 , 10으로 갈거구요 이 위치는 1초만에 올 수 있었으므로

방문배열에 1을 할당해주면서 Queue에 넣어줍니다. 해당 좌표들에서 다른 좌표로 또 이동해야되니까요 이 땐 2가 되고 쭉쭉쭉 3.. 4.. 5 초만에 갈 수 있는 좌표들은 방문배열에 초로 할당이 되겠죠!

이렇게 쭉쭉 뻗어나가다가 동생이 위치한 k를 발견한다면 그 때의 시간을 출력해주면 최소 시간이 됩니다! 구현은 간단하죠!?

단 한가지 주의할 점은 동생과 수빈이의 위치가 같을때 즉 n == k 일 때는 예외적으로 0을 출력해주어야합니다!

 

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

var array = Array(repeating: -1, count: 100001)
var idx = 0
func bfs() {
    var queue = [n]
    array[n] = 0
    
    while idx < queue.count {
        let value = queue[idx]
        idx += 1
        
        for next in [value-1,value+1,value*2] {
            if next < 0 || next > 100000 {
                continue
            }
            
            if next == k {
                array[next] = array[value] + 1
                print(array[k])
                return
            }
            
            if array[next] == -1 {
                array[next] = array[value] + 1
                queue.append(next)
            }
        }
    }
}
if n == k { print(0) } else {
    bfs()
}

저는 이번 문제에서 Queue가 비었는지 확인하고 POP을 하는 작업에서 removeFirst()를 사용하지 않고 인덱스를 통해 접근했습니다.

이번 문제에선 시간초과가 나지 않긴 합니다만!

둘 다 해보니 확실히 시간 효율 면에서 다르더라구요. removeFirst()를 쓰지 않고 작성하는 버릇을 들여야할 것 같습니다!

아래가 removeFirst 사용 위에가 index사용한 풀이입니다.