[Swift] 백준 13913 - 숨바꼭질 4

문제 바로가기

관련 문제인 숨바꼭질을 풀었다면 조금은 쉽게 풀이 가능하다

동생을 찾는 시간을 구하는 건 bfs로 가능한 데
찾는 경로를 저장하는 방법을 어떻게 구현할 지 애를 먹었다ㅠ

처음엔, 재귀함수를 사용해서 풀이했는데 시간초과가 났다
그래서 이번엔 footPrints[]배열을 사용해서
[x-1, x+1, x*2]중 만양 x -1로 이동가능하다면
footPrints[x-1] = x 을 넣어 나중에 그 경로를 거꾸로 찾아갈 수 있도록 하였다.

func bfs()

bfs함수에서 수민이가 동생을 찾는 가장 빠른 시간과 footPrints값을 넣어주는 작업을 수행한다.

var queue = [Int]()
var check = Array(repeating: false, count: 100001)
var footPrints = Array(repeating: -1, count: 100001)
var time = 0

func bfs(_ start: Int) {
	queue.append(start)
    check[start] = true
    
    while !check[destination] {
    	time += 1
    	for _ in 0..<queue.count {
        	let node = queue.removeFirst()
            
            for i in [node + 1, node - 1, node * 2] {
            	if 0...100000 ~= i && !check[i] {
                	check[i] = true
                    queue.append(i)
                    footPrints[i] = node
                }
            }
        }
    }
    print(time)
}

• 수빈이와 동생은 0~100000사이에 위치하기때문에 footPrints를 수빈이와 동생이 위치할 수 없는 -1 값을 가지는 배열로 만들었다.

prior

footPrints배열을 사용해서 경로를 찾는 방법이다.

var prior = footPrints[destination]
results.append(destination)
while prior != -1 {
	results.append[prior]
	prior = footPrints[prior]
}

results.reverse()
print(results.map{String($0)}.joined(separator:" "))

최종 코드

import Foundation

let location = readLine()!.split(separator: " ").map {Int(String($0))!}
let start = location[0]
let destination = location[1]

var queue = [Int]()
var time = 0
var check = Array(repeating: false, count: 100001)
var footPrints = Array(repeating: -1, count: 100001)
var result = [Int]()

func bfs(_ start:Int) {
    queue.append(start)
    check[start] = true
    
    while !check[destination] {
        time += 1
        for _ in 0..<queue.count {
            let node = queue.removeFirst()
            
            for i in [node+1, node-1, node*2] {
                if 0...100000 ~= i && !check[i]{
                    queue.append(i)
                    footPrints[i] = node
                    check[i] = true
                }
            }
        }
    }
    print(time)
}

bfs(start)
var prior = footPrints[destination]
result.append(destination)
while prior != -1 {
    result.append(prior)
    prior = footPrints[prior]
}

result.reverse()
print(result.map{String($0)}.joined(separator: " "))