BOJ 13460 구슬 탈출 2 swift

문제 링크 : https://www.acmicpc.net/problem/13460

 

 

문제 해설

빨간 구슬을 10번 이하로 기울여 구멍으로 빼내야하는 문제입니다.

파란 구슬이 구멍에 빠지면 실패입니다.

한 번 기울이면 구슬은 해당 방향으로 끝까지 굴러갑니다. (벽 앞에서 멈추거나, 구멍에서 빠짐)

최소 횟수를 구하는 BFS 문제입니다.

 

가장 기초적인 BFS는 움직여야하는 좌표가 1개였기 때문에 visited 배열이 2차원으로 선언해도 충분했었지만, 해당 문제는 좌표 2개를 움직이고 상태를 저장해야 하기 때문에 4차원 배열이 필요합니다.(빨강 xy, 파랑 xy)

그리고 다른 BFS와 다르게 한쪽 방향으로 끝까지 움직여야 합니다. 그래서 움직임을 처리하는 함수를 선언해주었습니다.

구슬끼리는 같은 좌표에 존재할 수 없기 때문에 같은 좌표에 존재한다면 뒤늦게 온 구슬을 한칸 뒤로 돌립니다.

 

코드

import Foundation

let input = readLine()!.split(separator: " ").compactMap { Int($0) }
let n = input[0]
let m = input[1]

var board: [[Character]] = []
var redX = 0, redY = 0
var blueX = 0, blueY = 0

for i in 0..<n {
    let rowChars = Array(readLine()!)
    var row: [Character] = []
    for (j, ch) in rowChars.enumerated() {
        row.append(ch)
        if ch == "R" {
            redX = i
            redY = j
            row[j] = "."
        } else if ch == "B" {
            blueX = i
            blueY = j
            row[j] = "."
        }
    }
    board.append(row)
}

struct State {
    var rx: Int
    var ry: Int
    var bx: Int
    var by: Int
    var cnt: Int
}

func roll(_ x: Int, _ y: Int, dirX: Int, dirY: Int, board: [[Character]]) -> (nx: Int, ny: Int, fell: Bool, moved: Int) {
    var cx = x
    var cy = y
    var moved = 0
    while true {
        let nx = cx + dirX
        let ny = cy + dirY
        if board[nx][ny] == "#" { // wall
            break
        }
        cx = nx
        cy = ny
        moved += 1
        if board[cx][cy] == "O" { // hole
            return (cx, cy, true, moved)
        }
    }
    return (cx, cy, false, moved)
}

let directions: [(Int, Int)] = [(0,1), (0,-1), (1,0), (-1,0)]

var visited = Array(
    repeating: Array(
        repeating: Array(
            repeating: Array(repeating: false, count: m),
            count: n
        ),
        count: m
    ),
    count: n
)

var queue: [State] = []
queue.append(State(rx: redX, ry: redY, bx: blueX, by: blueY, cnt: 0))
visited[redX][redY][blueX][blueY] = true

while !queue.isEmpty {
    let cur = queue.removeFirst()
    if cur.cnt >= 10 {
        continue
    }

    for (dx, dy) in directions {
        let r = roll(cur.rx, cur.ry, dirX: dx, dirY: dy, board: board)
        let b = roll(cur.bx, cur.by, dirX: dx, dirY: dy, board: board)

        if b.fell {
            continue
        }
        if r.fell {
            print(cur.cnt + 1)
            exit(0)
        }

        var nrx = r.nx, nry = r.ny
        var nbx = b.nx, nby = b.ny

        if nrx == nbx && nry == nby {
            if r.moved > b.moved {
                nrx -= dx
                nry -= dy
            } else {
                nbx -= dx
                nby -= dy
            }
        }

        if !visited[nrx][nry][nbx][nby] {
            visited[nrx][nry][nbx][nby] = true
            queue.append(State(rx: nrx, ry: nry, bx: nbx, by: nby, cnt: cur.cnt + 1))
        }
    }
}

print(-1)