[백준]BOJ 13460: 구슬 탈출 2 - Swift/BFS

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

13460번: 구슬 탈출 2

문제

풀이

기울이는 방향에 따라서 구슬이 이동하므로, 구슬이 이동할 수 있는 방향은 상하좌우임을 알 수 있다. 이 때, 한 번 기울일 때 마다 구슬의 최종 위치는 하나가 나오므로, BFS를 이용해서 문제를 해결할 수 있다. 

 

문제의 조건을 정리하면 다음과 같다.

1. 한 칸에는 구슬 한 개만 들어갈 수 있다.

2. 한 번 기울이면 구슬이 더 이상 움직이지 못할 때 까지 움직인다.

3. 10번 이하의 횟수로만 기울인다.

 

1, 2 조건을 조합하면 구슬이 다른 구슬을 만나도 벽을 만난것과 같음을 알 수 있고, 따라서 구슬이 겹친 경우에는 처리를 해줘야 한다.

단순히 겹친 구슬들 중 더 많이 움직인 구슬을 한 칸 뒤로 옮겨주면 된다.

코드

import Foundation

struct Marble: Hashable {
    var rr: Int
    var rc: Int
    var br: Int
    var bc: Int
    
    init(_ tuple: ((Int, Int), (Int, Int))) {
        self.rr = tuple.0.0
        self.rc = tuple.0.1
        self.br = tuple.1.0
        self.bc = tuple.1.1
    }
}

struct Queue {
    var queue = [(((Int, Int), (Int, Int)), Int)]()
    var ptr = 0
    var isEmpty: Bool {
        queue.count <= ptr
    }

    mutating func push(_ v: (((Int, Int), (Int, Int)), Int)) {
        queue.append(v)
    }

    mutating func pop() -> (((Int, Int), (Int, Int)), Int) {
        let firstValue = queue[ptr]
        ptr += 1
        if ptr > 100_000 {
            queue = Array(queue[ptr...])
            ptr = 0
        }
        return firstValue
    }
}

func bfs(_ start: ((Int, Int), (Int, Int))) {
    let moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    var queue = Queue()
    queue.push((start, 1))
    var isVisited: Set<Marble> = []
    isVisited.insert(Marble(start))
    
    while !queue.isEmpty {
        let (curStat, curCount) = queue.pop()
        if curCount > 10 {
            print(-1)
            exit(0)
        }
        for move in moves {
            var (nextRed, nextBlue) = curStat
            var (rCount, bCount) = (0, 0)
            while graph[nextRed.0 + move.0][nextRed.1 + move.1] != "#" && graph[nextRed.0][nextRed.1] != "O" {
                nextRed.0 += move.0
                nextRed.1 += move.1
                rCount += 1
            }
            while graph[nextBlue.0 + move.0][nextBlue.1 + move.1] != "#" && graph[nextBlue.0][nextBlue.1] != "O" {
                nextBlue.0 += move.0
                nextBlue.1 += move.1
                bCount += 1
            }
            if graph[nextBlue.0][nextBlue.1] == "O" {
                continue
            }
            if graph[nextRed.0][nextRed.1] == "O" {
                print(curCount)
                exit(0)
            }
            if nextRed == nextBlue {
                if rCount > bCount {
                    nextRed.0 -= move.0
                    nextRed.1 -= move.1
                } else {
                    nextBlue.0 -= move.0
                    nextBlue.1 -= move.1
                }
            }
            if isVisited.contains(Marble((nextRed, nextBlue))) {
                continue
            }
            isVisited.insert(Marble((nextRed, nextBlue)))
            queue.push(((nextRed, nextBlue), curCount + 1))
        }
    }
    print(-1)
}

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (nm[0], nm[1])
var graph = [[Character]]()
for _ in 0..<n {
    graph.append(Array(readLine()!))
}

var (startRed, startBlue) = ((0, 0), (0, 0))
for row in 0..<n {
    for column in 0..<m {
        if graph[row][column] == "R" {
            startRed = (row, column)
        } else if graph[row][column] == "B" {
            startBlue = (row, column)
        }
    }
}

bfs((startRed, startBlue))