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

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 1697 숨바꼭질" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

1697번: 숨바꼭질

 

---

풀이

이번 문제는 bfs 문제입니다.

 

queue에 현재 위치인 dot과 걸린 시간인 sec를 튜플로 담습니다.

다음 노드인 dot+1, dot-1, dot*2를 탐색하면서 K와 동일하면 반복을 종료하고 sec를 출력해 줍니다.

 

이 문제는 다른 bfs 문제보다 input size가 커서 메모리 초과, 시간 초과가 발생할 가능성이 높습니다.

따라서 Swift로는 최대한 최적화를 해야 무사 통과를 할 수 있습니다.

 

저는 다른 문제에서는 visited를 contains를 이용해 사용했었는데 이번 문제에서는 불가능 했습니다.

또한 queue에 무조건 append를 하고 꺼내서 K를 체크하면 메모리 초과가 나더라고요.

이런 작은 부분을 잘 고려해서 문제를 푸시길 바랍니다..!

 

반성 반성

사실 문제 카테고리를 보지 않고 이 문제를 접했을 때 과연 bfs를 떠올릴 수 있었을까?하는 생각이 들더라고요.

 

또, visited를 최대 입력 수만큼 할당 해놓는 방법이 싫어 contains()를 이용했었는데 이번 문제에서는 이 고집때문에

시간초과를 여러 번 보게 되었습니다.

메모리 효율보다는 시간복잡도에 더 신경 써야겠습니다.

 

---

전체 코드

//1697 숨바꼭질
import Foundation

let MAX = 100000

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

if N == K {
    print(0)
} else {
    var queue: [(dot: Int, sec: Int)] = [(N, 0)]
    var visited: [Bool] = Array(repeating: false, count: MAX+1)
    var index = 0
    while index < queue.count {
        let node = queue[index]
        index += 1
        
        for i in 0..<3 {
            var nextDot = 0
            switch i {
            case 0: nextDot = node.dot - 1
            case 1: nextDot = node.dot + 1
            default: nextDot = node.dot * 2
            }
            
            if nextDot == K {
                result = node.sec + 1
                index = queue.count
                break
            } else {
                if nextDot < 0 || nextDot > MAX || visited[nextDot] {
                    continue
                }
                visited[nextDot] = true
                queue.append((nextDot, node.sec+1))
            }
        }
    }
    
    print(result)
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.