1697 숨바꼭질

Today 8/16

BFS

queue를 사용하는 FIFO형식의 탐색방법이다.

숨바꼭질 (My Code)

//1697 숨바꼭질
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])

var queue = [(0, N)]
var count = 0
var visited = Array(repeating: false, count: 100001)
visited[N] = true

func BFS() {
    let node = queue[count]
    
    if node.1 == K {
        print(node.0)
        return
    }
    for i in [node.1-1, node.1+1, node.1*2] {
        if i >= 0 && i <= 100000 && !visited[i] {
            queue.append((node.0+1, i))
            visited[i] = true
        }
    }
    count += 1
    BFS()
}

BFS()

저번에 풀었던 문제인데 다시 개념을 잡고싶어서 다시 풀어봤다.

처음에는 이게 왜 BFS인지 몰랐는데 3가지 경우의 수로 뻗어나가고, 그 중에서 최소 경로를 구하는 것이라 생각하니 왜 BFS인지 알았다.

이렇게 재귀함수로 풀었는데 32ms가 나와서 예전에 12ms는 어떻게 나왔나 다시 공부해보았다.

숨바꼭질 (My Code)

//1697 숨바꼭질
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N,K) = (input[0],input[1])

var queue = [(0,N)]
var index = 0
var visited = Array(repeating: false, count: 100001)
visited[N] = true

while index < queue.count {
    let node = queue[index]
    if node.1 == K {
        print(node.0)
        break
    }
    for i in [node.1+1, node.1-1, node.1*2] {
        if i <= 100000 && i >= 0 && !visited[i] {
            queue.append((node.0+1, i))
            visited[i] = true
        }
    }
    index += 1
}

똑같이 while문 써서 풀었다. 유의미한 차이는 모르겠는데 20ms로 더 빠르게 나왔다.

중요한점은

0 ≤ i ≤ 100001 범위 정해주는 것과, visited 설정, index로 removeFirst()안하게 해주는 것. 이런 조건들 설정해주지 않으면 시간초과난다.

depth를 알아보기 위해 queue를 tuple로 만들어주는 것

정답 걸러내는 if문을 for문 전에 넣어야 N == K 일 때 걸러낼 수 있다. 안그러면 밑에서 따로 설정해줘야 한다.

이 문제에서는 break가 있어서 상관없지만 index로 queue를 관리할 때는 while문에 index < queue.count를 넣어서 제어를 해주어야 한다.