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

BOJ 1697 숨바꼭질

 

✅ 일단 이 문제를 풀면서 그동안 자주 사용했던 BFS 패턴을 적용했는데, 시간 초과로 통과할 수 없었음.

질문란이나 다른 분들이 Swift는 Queue를 만들어야 통과한다고 제시하는 의견도 있었는데, 내가 보니까 이게 그렇게 큰 영향을 주는 것 같지는 않았음.

 

그러다가 정말 좋은 블로그를 발견해서 이 분의 아이디어를 기반으로 아주 약간만 개선하고 이 분의 코드를 학습함.

 

스위프트는 유독 2차원 배열보다 차라리 1차원 배열에 튜플을 넣는게 속도가 엄! 청! 나! 게! 빠름

그러니까 2차원 배열 만들지말자..!

 

아래는 시간 비교이다.

2차원 배열

 

1차원 배열 + 튜플

✅ 코드

 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