[Swift] BOJ 1697 숨바꼭질 (2차원 배열보다 1차원 튜플 배열)

BOJ 1697 숨바꼭질

 

접근 방식

 

위치 하나를 상태로 두는 BFS. 각 위치 now에서 now-1, now+1, now*2 세 방향으로 이동하고, 목표에 처음 닿는 순간의 이동 횟수가 최단 시간이 됨. 크기 100001짜리 visited 배열로 이미 지난 위치를 막음.

 

처음에는 늘 쓰던 BFS 패턴을 그대로 적용했는데 시간 초과로 통과하지 못함. 질문란에는 Swift는 Queue를 직접 구현해야 통과한다는 의견도 있었으나, 직접 확인해보니 큰 영향은 없었음. 결국 다른 분의 풀이(참고)를 학습해 정리함.

 

실제로 속도를 가른 건 자료구조 형태였음. 스위프트에서는 2차원 배열보다 1차원 배열에 튜플을 담는 방식이 훨씬 빠름. 이 문제도 위치와 이동 횟수를 (now, count) 튜플로 1차원 큐에 담아 해결했고, 가능하면 2차원 배열은 만들지 않는 편이 나음.

 

아래는 시간 비교임.

 

 

 

코드

 

 let info = readLine()!.split(separator: " ").map{ Int(String($0))! }
        let subin = info[0] // 수빈이의 시작점
        let target = info[1] // 동생 위치
        var queue = [(subin, 0)] // 이동하는 수빈이의 위치와 해당 위치까지 가는데까지 걸린 시간을 튜플로 담음
        var found = false // 찾았는지 체크하는 불 변수
        var visited = Array(repeating: false, count: 100001) // 이미 수빈이가 다녀간 자리들을 체크해주기 위함
        
        var index = 0
        
        if subin == target { print(0) } // 처음부터 수빈이와 동생의 위치가 같을 경우 => 바로 끝
        else {
            while true {
                let (now, now_count) = queue[index]
                index += 1
                var next = 0 // 수빈이가 이동할 위치를 담을 변수
                
                for i in 0..<3 {
                    if i == 0 { next = now - 1 } // X-1 이동
                    else if i == 1 { next = now + 1 } // X+1 이동
                    else { next = now * 2 } // X*2 이동
                    
                    if next < 0 || next > 100000 || visited[next] == true { continue } // 예외!
                    if next == target { found = true; break } // 찾았을 경우
                    visited[next] = true // 수빈이가 지나간 곳은 1로 체크헤주기 (같은 곳 또 지나갈 필요 전혀x)
                    queue.append((next, now_count + 1)) // 수빈이가 이동할 위치와 그 위치까지 가는데 걸린 시간 추가!
                }
                
                if found { print(now_count+1); break } // 결과 출력
            }
        }

 

참고

 

https://seolhee2750.tistory.com/128

 

[Swift Algorithm] 숨바꼭질 BOJ #1697 문제 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위