문제 정보



두 문제가 숨바꼭질 2 문제와 풀이가 유사해서 같이 풀어보았습니다.

[13549 숨바꼭질 3]

image

[13913 숨바꼭질 4]

image

13549 숨바꼭질 3

풀이

숨바꼭질 3 문제는 숨바꼭질 2 문제와의 차이점이 2*X의 위치로 이동할 때와 X-1 or X+1의 위치로 이동할 때의 시간이 각각 0과 1로 차이가 있다는 점이다.
그래서 queue에 이동할 위치의 좌표와 depth를 넣어줄 때 2*X의 위치로 이동할 경우에는 cost에 1을 더해주지 않았다.
알고리즘을 작성할 때, 2*X -> X-1 -> X+1 순서로 작성해줘야 가장 적은 cost를 구할 수 있다.

    //방문할 수 있는 위치인지 확인하고 X-1, X+1 이동시 cost+1, Xx2 이동시 cost를 넣어준다
        if isVisitedPossible(num*2) {
            queue.pushLast((num*2, cost))
        }
        if isVisitedPossible(num-1) {
            queue.pushLast((num-1, cost+1))
        }
        if isVisitedPossible(num+1) {
            queue.pushLast((num+1, cost+1))
        }

코드

class Queue<T> {
    var inbox: [T]
    var outbox: [T] = []
    
    var count: Int {
        return inbox.count + outbox.count
    }
    
    var isEmpty: Bool {
        return inbox.isEmpty && outbox.isEmpty
    }
    
    init(_ queue: [T]) {
        inbox = queue
    }
    
    func pushLast(_ element: T) {
        inbox.append(element)
    }
    
    func pushFirst(_ element: T) {
        outbox.append(element)
    }
    
    func popLast() -> T {
        if inbox.isEmpty {
            inbox = outbox.reversed()
            outbox.removeAll()
        }
        return inbox.popLast()!
    }
    
    func popFirst() -> T {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.popLast()!
    }
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var visited = Array(repeating: false, count: 100001)

//방문하지 않았고, 순간이동할 수 있는 위치인지 확인
func isVisitedPossible(_ x: Int) -> Bool {
    if ((0...100000) ~= x) && !visited[x] {
        return true
    }
    else{
        return false
    }
}
func findSister(_ startX: Int) {
    // 수빈이 위치 queue에 넣고 visited true로 초기화.
    let queue = Queue([(startX, 0)])
    visited[startX] = true
    
    //queue가 비었을 때까지
    while !queue.isEmpty {
        let (num, cost) = queue.popFirst()
        // 큐에서 pop할 때 방문처리
        visited[num] = true
        
        // 동생을 찾은 경우 cost 출력
        if num == K {
            print(cost)
            return
        }
        
        //방문할 수 있는 위치인지 확인하고 X-1, X+1 이동시 cost+1, Xx2 이동시 cost를 넣어준다
        if isVisitedPossible(num*2) {
            queue.pushLast((num*2, cost))
        }
        if isVisitedPossible(num-1) {
            queue.pushLast((num-1, cost+1))
        }
        if isVisitedPossible(num+1) {
            queue.pushLast((num+1, cost+1))
        }
    }
}
findSister(N)

13913 숨바꼭질 4

풀이

동생을 최소 시간으로 찾을 때의 경로를 나타내야 하므로 prev라는 배열에 자신의 이전 depth의 값을 넣어줘서 기억한 후
queue에서 pop한 값이 동생의 위치일 경우 그 경로를 출력해준다.

코드

class Queue<T> {
    var inbox: [T]
    var outbox: [T] = []
    
    var count: Int {
        return inbox.count + outbox.count
    }
    
    var isEmpty: Bool {
        return inbox.isEmpty && outbox.isEmpty
    }
    
    init(_ queue: [T]) {
        inbox = queue
    }
    
    func pushLast(_ element: T) {
        inbox.append(element)
    }
    
    func pushFirst(_ element: T) {
        outbox.append(element)
    }
    
    func popLast() -> T {
        if inbox.isEmpty {
            inbox = outbox.reversed()
            outbox.removeAll()
        }
        return inbox.popLast()!
    }
    
    func popFirst() -> T {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.popLast()!
    }
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var visited = Array(repeating: false, count: 100001)
var prev = Array(repeating: 0, count: 100001)
var count = 0
var minDepth = 100001

//방문하지 않았고, 순간이동할 수 있는 위치인지 확인
func isVisitedPossible(_ x: Int) -> Bool {
    if ((0...100000) ~= x) && !visited[x] {
        return true
    }
    else{
        return false
    }
}
func printPath(_ num: Int) {
    var tmp = num
    var tempArray: [Int] = []
    while tmp != N {
        tempArray.append(tmp)
        tmp = prev[tmp]
    }
    tempArray.append(N)
    for i in tempArray.reversed() {
        print(i, terminator: " ")
    }
}
func findSister(_ startX: Int) {
    if N == K {
        print(0)
        print(N)
        return
    }
    let queue = Queue([(startX, 0)])
    while !queue.isEmpty {
        var (num, depth) = queue.popFirst()  
        for next in [num+1, num-1, num*2] {
            if isVisitedPossible(next) {
                visited[next] = true
                queue.pushLast((next,depth+1))
                prev[next] = num
                if next == K {
                    print(depth+1)
                    printPath(next)
                    return
                }
            }
        }
    }
}

findSister(N)