[Swift] 백준 1697: 숨바꼭질

문제 사이트

1697번: 숨바꼭질

 

---

 알고리즘 

 

1. BFS 탐색을 하는데, 동생위치에서의 depth를 구해야한다.

---

 나의 코드 

var visited = [Bool](repeating: false, count: Int(1e5)+1)
let input = readLine()!.split(separator: " ").map{ Int($0)! }
var depth = [Int](repeating: 0, count: Int(1e5)+1)
var queue = [input[0]]
visited[input[0]].toggle()
while true {
    let node = queue.removeFirst() // 제일 앞에 원소 pop
    if node == input[1]{ // 현재 위치 == 동생위치면 종료
        break
    }
    for i in 0..<3 {
        var next: Int // 갈 수 있는 위치 탐색
        if i == 0 { next = node-1 }
        else if i == 1 { next = node+1 }
        else { next = node*2 }
        
        if vaild(n: next){
            queue.append(next)
            depth[next] = depth[node] + 1 // depth 계산
            visited[next].toggle() // 방문처리
        }
    }
}
print(depth[input[1]])

func vaild(n: Int) -> Bool {
    if  n < 0 || n > 100000 || visited[n] { // Index error 방지 및 방문여부 확인
        return false
    }
    return true // index error가 발생하지 않고, 방문하지 않은 경우에만 true반환
}

---

 KeyPoint 

📍depth 계산
     단순 연산 횟수가 아닌, 그래프 상 depth를 계산해야한다.

📍지수 표현
     1e5 = 1 * 10^5 이라는 뜻!

📍BFS의 방문처리하는 시간
     (이것때문에 엄청 잡아먹음 ㅠㅠ)