[Swift][BFS] 백준 1600번 (말이 되고픈 원숭이)

요구능력

BFS

 

문제풀이

기본적인 BFS에서 우리는 최소의 이동횟수를 구해야한다.

어느부분에서 점프했을때 최소의 이동거리인지 알 수 있는 방법이 없기 때문에 BFS를 돌아주면서 방문하는 곳마다 점프하는 경우를 큐에 넣어준다. 이때 점프횟수가 남아있을 때만 점프를 해준다.

이 문제에서 가장 핵심포인트는 3차원 배열을 사용해서 한 지점에 도착했을 때 몇번의 점프가 남았는지를 적어주는 것이다.

무슨 말이냐면 만약 내가 점프를 한번도안하고 (0,0)부터 (x,y)까지 이동했을 경우가 있고, 점프를 한번하고 (x,y)까지 이동했을 경우가 있다고 가정해보자.

근데 같이 방문처리를 해줘버리면, 이게 겹치게된다.

따로 관리하기위해서 3차원으로 방문처리를 해주게된것이다.

그리고 도착지점에 도착했을 때 바로 break를 걸어준 이유는 최소로 이동한경우가 가장 빠른 경우이기 때문이다.

예를 들어서 점프를 2번할 수 있는경우라면, 점프를 2번 모두 사용한 이동횟수가 가장 적고 빨리 도착할 것이다.

 

후기

난이도가 어려운편은 아닌거 같은데 정답률이 엄청낮다..

 

코드

var k = Int(String(readLine()!))!
var wh = readLine()!.split(separator: " ").map{Int(String($0))!}
var w = wh[0]
var h = wh[1]
var arr = [[Int]]()
var dx = [-1, 1, 0, 0]
var dy = [0, 0, -1, 1]
var horseDx = [-2, -1, -2, -1, 1, 2, 2, 1]
var horseDy = [-1, -2, 1, 2, -2, -1, 1, 2]

for _ in 0..<h{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

func bfs() -> Int{
    var queue = [(Int, Int, Int, Int)]()//x, y, 이동횟수, k
    var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 31), count: 201), count: 201)
    queue.append((0, 0, 0, k))
    visited[0][0][k] = true
    var result = -1
    var idx = 0
    while queue.count > idx{
        let (x, y, move, k) = queue[idx]
        idx += 1
        if x == h - 1 && y == w - 1 {
            result = move
            break
        }

        if k > 0 {
            for i in 0..<8{
                let nx = horseDx[i] + x
                let ny = horseDy[i] + y

                if nx < 0 || ny < 0 || nx >= h || ny >= w {continue}
                if arr[nx][ny] == 1 || visited[nx][ny][k - 1] {continue}
                queue.append((nx, ny, move + 1, k - 1))
                visited[nx][ny][k - 1] = true
            }
        }
        for i in 0..<4{
            let nx = x + dx[i]
            let ny = y + dy[i]
            if nx < 0 || ny < 0 || nx >= h || ny >= w {continue}
            if arr[nx][ny] == 1 || visited[nx][ny][k] {continue}
            queue.append((nx, ny, move + 1, k))
            visited[nx][ny][k] = true
        }


    }
    return result
}
print(bfs())