[1600] 말이 되고픈 원숭이

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

[4179] 불! 문제보다는 체감상 쉽게 다가왔다. 불! 문제에서 너무 고생해서 그랬나 보다. 물론 한 번에 통과하진 못했고, 결국 답을 찾아보았지만 조금만 더 깊이 생각했으면 답에 도달하지 않았을까 싶다.

 

풀이

늘 bfs문제를 풀듯이, 상하좌우 좌표의 확인과 말의 이동방식의 좌표 확인 과정을 추가해서 경로를 탐색하면 된다. 중요한 점은 말의 움직임은 k번까지만 가능하고, 말의 움직임과 원숭이의 움직임에 대해 순서가 뒤섞여서 움직일 수 있다는 점이다. 해당 부분에 대한 처리가 어설퍼서 처음에는 오답 판정을 받았다. 

 

큐에는 다음 좌표와 말의 움직임을 몇번 사용하였는지, 그리고 지금까지의 총 이동 횟수를 담아 확인했다. 이후 방문 여부를 확인하는 visited 배열을 3차원으로 생성하는 것이 핵심이다. visited[k][x][y] 배열을 통해 k번째 말의 움직임과 일반적인 움직임의 조합으로 경로를 탐색한다. 각 k번째 visited 배열에는 해당 횟수에서 이동 가능한 말의 움직임 + 원숭이의 움직임에 대한 방문 여부를 확인하고 경로탐색을 수행하면 된다. 설명보단 코드로 보는 것이 이해하기 더 쉬울 것이다.

 

오답 코드

해당 코드에서는 말의 움직임에 대해 깊이 고민하지 않고, 일반적인 visited배열을 사용하여 오답 판정을 받았다.

import Foundation

let k = Int(readLine()!)!
let wh = readLine()!.split(separator: " ").map{Int($0)!}
let w = wh[0]
let h = wh[1]
var ans = -1
var length = 0

var map = Array(repeating: Array(repeating: 0, count: w), count: h)
var visited = Array(repeating: Array(repeating: false, count: w), count: h)
for x in 0..<h{
    let land = readLine()!.split(separator: " ").map{Int($0)!}
    for y in 0..<w{
        map[x][y] = land[y]
    }
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
let hx = [-1,-2,-2,-1,1,2,2,1]
let hy = [-2,-1,1,2,2,1,-1,-2]

func bfs(){
    var q = [[0,0,k,length]]
    var dq = [[Int]]()
    while !q.isEmpty{
        dq = q.reversed()
        q.removeAll()
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let x = curr[0]
            let y = curr[1]
            let cnt = curr[2]
            let len = curr[3]
            if x==h-1 && y==w-1{
                ans = len
                return
            }
            
            if cnt>0{
                for i in 0..<8{
                    let nx = x+hx[i]
                    let ny = y+hy[i]
                    if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
                    if !visited[nx][ny]{
                        visited[nx][ny] = true
                        q.append([nx,ny,cnt-1,len+1])
                    }
                }
            }
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
                if !visited[nx][ny]{
                    visited[nx][ny] = true
                    q.append([nx,ny,cnt,len+1])
                }
            }
        }
    }
}
visited[0][0] = true
bfs()
print(ans)

 

정답 코드

import Foundation

let k = Int(readLine()!)!
let wh = readLine()!.split(separator: " ").map{Int($0)!}
let w = wh[0]
let h = wh[1]
var ans = -1

var map = Array(repeating: Array(repeating: 0, count: w), count: h)
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 31), count: w), count: h)
for x in 0..<h{
    let land = readLine()!.split(separator: " ").map{Int($0)!}
    for y in 0..<w{
        map[x][y] = land[y]
    }
}
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
let hx = [-1,-2,-2,-1,1,2,2,1]
let hy = [-2,-1,1,2,2,1,-1,-2]

func bfs(){
    var q = [[0,0,0,0]]
    var dq = [[Int]]()
    while !q.isEmpty{
        dq = q.reversed()
        q.removeAll()
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let x = curr[0]
            let y = curr[1]
            let cnt = curr[2]
            let length = curr[3]
            if x==h-1 && y==w-1{
                ans = length
                return
            }
            
            if cnt<k{
                for i in 0..<8{
                    let nx = x+hx[i]
                    let ny = y+hy[i]
                    if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
                    if !visited[nx][ny][cnt+1]{
                        visited[nx][ny][cnt+1] = true
                        q.append([nx,ny,cnt+1,length+1])
                    }
                }
            }
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=h || ny<0 || ny>=w || map[nx][ny]==1{continue}
                if !visited[nx][ny][cnt]{
                    visited[nx][ny][cnt] = true
                    q.append([nx,ny,cnt,length+1])
                }
            }
        }
    }
}
visited[0][0][0] = true
bfs()
print(ans)