백준 - 구슬 탈출 1, 2, 4, 13459, 13460, 15653 - swift

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

13459번: 구슬 탈출

 

조금 난이도 있는 구현, bfs 문제라고 생각한다.

구현에 있어서 고려할 요소가 몇 개 있다.

기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때까지이다.

즉, 좌, 우, 위, 아래 움직일 때 한 칸만 움직이는 것이 아닌 끝까지 움직이도록 해야 한다.
그리고 더 이상 움직이지 않을 때는, 벽에 부딪히거나, 또는 다른 구슬에 부딪힌 경우다.

그러므로, 아래와 같은 테스트 케이스에서 0이 나올 수밖에 없는 이유다.

3 10
##########
#.O....RB#
##########

여기서 더 고려할 점은, 어느 쪽으로 움직이든, 누가 먼저 움직이는지를 알아야 한다는 점이다.
....RB... 이렇게 있는 경우에 왼쪽으로 움직일 경우 Red부터 먼저 움직인다.
하지만 오른쪽으로 움직일 경우에는 Blue부터 움직인다.

즉, 누가 먼저 벽에 부딪힌 다음에, 그다음 구슬이, 먼저 움직인 구슬에 부딪혀야 한다. ( 벽이 아닌 )
마찬가지로 좌, 우뿐만 아니라 위 아래도 누가 먼저 움직 일지를 알아야 한다.
귀찮지만, 각각 움직일 방향을 분기 처리하여, 좌우 일 때는, 열 방향으로 구슬끼리 값을 비교하고,
위아래일 때는 행방향으로 구슬끼리의 값을 비교한다.


bfs는 다음과 같이 진행했다.
큐에 red구슬 위치, blue구슬 위치, 움직인 횟수를 넣어주도록 한다.
그리고, 4방향에 맞춰서, 어떤 구슬이 먼저 움직일지 파악하고,
각각 구슬들을 끝까지 움직여준다.
그리고 구멍에 빠졌을 경우나 벽에 부딪혔거나, 다른 구슬에 부딪힌 경우에 구슬을 멈춘다.
그렇게 멈춘 구슬을 판별하여, red구슬만 구멍에 빠지고, blue구슬은 남아있는 경우에 바로 return 하도록 했다.


별다른 방문처리 없이도 이렇게 풀면 통과는 된다. 다만 조금 오래 걸린다.


여기서 시간을 훨씬 단축할 수 있는 방법은,
방문처리를 하는 것이다.
check [ ri ] [ rj ] [ bi ] [ bj ] = red구슬 위치 i, j와 blue구슬 위치 i, j일 때, 해당 위치에 방문을 했는지 Bool타입 4차원 배열.
로 정의한다.

하나의 구슬만 방문 처리하게 되면, 한 구슬이 해당 위치에 또 방문했어도, 다른 구슬의 위치가 달라졌을 수도 있기 때문이다.
그러므로, 두 구슬 모두 고려하여 방문처리하도록 한다.

그렇게 되면 244ms -> 8ms로 줄어드는 마법을 볼 수 있다.


+ 추가적으로 구슬 탈출 2 13460번 문제는 문제 자체는 같고, 최소 횟수로 탈출하는 문제 이므로,
이미 bfs를 통해 최소 움직임이 보장되고 있으므로, return 1을 하지 않고 return f.count + 1을 하면 된다.

 

+ 구슬 탈출 4 15653번 문제도 문제 자체는 같고, 대신 10번 횟수 제한이 없다. 

bfs안에서 count == 10 인경우에 return 하는 코드만 삭제하면 통과 가능하다. 

 

 

구슬 탈출 1 코드

let inp = readLine()!.split(separator: " " ).map{Int(String($0))!}
let row = inp[0], col = inp[1]

var arr = [[String]]()
var redBall = (0,0)
var blueBall = (0,0)
for i in 0..<row {
    var l = readLine()!.map{String($0)}
    for j in 0..<col {
        if l[j] == "B" {
            l[j] = "."
            blueBall = (i,j)
        } else if l[j] == "R" {
            redBall = (i,j)
            l[j] = "."
        }
    }
    arr.append(l)
}

let dir = [(0,1),(0,-1),(1,0),(-1,0)]

func move(first: (Int, Int), second: (Int, Int), i: Int  ) -> ((Int,Int), (Int,Int)) {
    var nf = first
    var ns = second
    
    while true {
        let f = (nf.0+dir[i].0, nf.1+dir[i].1)
        if f.0>=row||f.1>=col||f.0<0||f.1<0||arr[f.0][f.1] == "#" {break}
        nf = f
        if arr[f.0][f.1] == "O"{
            break
        }
    }
    while true {
        let s = (ns.0+dir[i].0, ns.1+dir[i].1)
        if s.0>=row||s.1>=col||s.0<0||s.1<0||arr[s.0][s.1] == "#"{break}
        if s == nf, arr[nf.0][nf.1] != "O" {
            break
        }
        ns = s
        if arr[s.0][s.1] == "O"{
            break
        }
    }
    
    return (nf,ns)
}

func find() -> Int  {
    var queue: [(r: (Int,Int), b: (Int,Int), count: Int )] = [(redBall, blueBall,0)]
    var q = 0
    var check = Array(repeating: Array(repeating: Array(repeating: Array(repeating: false, count: col), count: row), count: col), count: row)
    check[redBall.0][redBall.1][blueBall.0][blueBall.1] = true
    while queue.count > q {
        let f = queue[q]
        q += 1
        if f.count == 10 {
            return 0
        }
        
        for i in 0..<4 {
            var nr = f.r
            var nb = f.b
            switch  i {
            case 0: //right
                if f.b.1 < f.r.1 {
                    (nr, nb) = move(first: f.r, second: f.b, i: i)
                } else {
                    (nb, nr) = move(first: f.b, second: f.r, i: i)
                }
            case 1: // left
                if f.b.1 > f.r.1 {
                    (nr, nb) = move(first: f.r, second: f.b, i: i)
                } else {
                    (nb, nr) = move(first: f.b, second: f.r, i: i)
                }
            case 2: //down
                if f.b.0 < f.r.0 {
                    (nr, nb) = move(first: f.r, second: f.b, i: i)
                } else {
                    (nb, nr) = move(first: f.b, second: f.r, i: i)
                }
            case 3: //up
                if f.b.0 > f.r.0 {
                    (nr, nb) = move(first: f.r, second: f.b, i: i)
                } else {
                    (nb, nr) = move(first: f.b, second: f.r, i: i)
                }
            default:
                print()
            }
            
            if check[nr.0][nr.1][nb.0][nb.1] { continue }
            if arr[nr.0][nr.1] == "O", arr[nb.0][nb.1] == "." {
                return 1
            } else if arr[nr.0][nr.1] == ".", arr[nb.0][nb.1] == "." {
                queue.append((nr,nb,f.count+1))
                check[nr.0][nr.1][nb.0][nb.1] = true
            }
        }
    }
    return 0
}

print(find())