백준 13460 구슬 탈출 2

출처: www.acmicpc.net/problem/13460

분류: 완전 탐색

---

접근방식

상하좌우로 회전시킬 수 있는 보드판 위에 빨강, 파랑 구슬, 빠져나갈 구멍이 있을 때 움직여서 빨간 구슬만 구멍에 넣어야 할 때 최소 횟수를 찾는 문제입니다. 단, 횟수가 10번을 초과하면 안됩니다.

판의 크기가 3 ~ 10 까지로 매우 작고 10번이라는 제한이 있기 때문에 모든 경우를 다 탐색해서 말그대로 완전 탐색으로 해결할 수 있습니다. 개인적으로 구현이 꽤나 까다로웠던 문제였습니다.

상하좌우로 다 해본다는 게 말은 쉽지만 생각보다 까다로웠습니다.
두 구슬은 겹칠 수 없기 때문에 다른 구슬이 앞에 있다면 그 구슬 뒤까지 움직여야 하고 말이죠...

구현 아이디어는 다음과 같습니다.

빨간 구슬과 파란 구슬은 계속 굴러다녀야 하기 때문에 처음의 좌표값을 저장하고
보드 판의 빨간 구슬과 파란 구슬은 "." 으로 바꿔서 비워줍니다.

그리고 재귀함수에 파란구슬과 빨간 구슬, 현재까지 이동횟수, 방향을 입력받아 새로운 위치를 계산합니다.
우선 그 방향으로 빨간 구슬과 파란 구슬을 갈 수 있는 데까지 한 칸씩 이동시킵니다.

주의할 점은 빨간 구슬을 구멍에 넣는 것이 목표지만 빨간 구슬과 파란 구슬은 둘다 빠지면 안됩니다.
 따라서 위치를 계산할 때는 빨간 구슬을 먼저 계산해줍니다. 해당 방향으로 한 칸씩 반복하다가 구멍을 찾으면 거기서 break 합니다.
그리고 파란 구슬을 계산하는데, 파란 구슬은 구멍을 찾으면 안되기 때문에 구멍을 만났다면 바로 return 합니다.
이렇게하면 빨간 구슬에서는 return이 아닌 break를 했기 때문에 둘다 빠지는 경우를 처리해줄 수 있습니다.
빨간 구슬과 파란 구슬의 반복문이 끝났으면 움직인 이후의 빨간 공이 구멍의 위치인지 체크해주고 최소값을 카운트해줍니다.

만약 빨간 구슬과 파란 구슬이 겹친다면 움직이기 이전의 위치를 계산해 더 뒤에 있어야 하는 녀석을 한 칸 뒤로 이동시켜줍니다.

만약 두 구슬 모두 움직임이 없었다면 이동할 수 없는 상태이기 때문에 바로 return 해줍니다.

 

해결방법

저는 Direction 열거형을 만들여서 move, back 함수를 만들어서 처리해줬습니다.
함수에서 움직이고 난 구조체 Point를 return 해주도록 구현했습니다.

그래서 구슬 위치가 "#" 인지 체크해서 "#"이면 뒤로 back 시켜줬습니다. 이런 방식이 아니고 먼저 갈 수 있는 곳인지 체크하는 방식이라면 이 과정은 없어도 될 것 같습니다.

let nm = readLine()!.split(separator: " ").map{Int($0)!}
var board = [[Character]]()
var minimumTry = Int.max
typealias Point = (r: Int, c: Int)
var redPoint = Point(r: 0, c: 0)
var bluePoint = Point(r: 0, c: 0)
var holePoint = Point(r: 0, c: 0)

for r in 0..<nm[0] {
    let row = Array(readLine()!)
    board.append(row)
    
    if let c = row.firstIndex(of: "B") {
        bluePoint = Point(r: r, c: c)
        board[r][c] = "."
    }
    if let c = row.firstIndex(of: "R") {
        redPoint = Point(r: r, c: c)
        board[r][c] = "."
    }
    if let c = row.firstIndex(of: "O") {
        holePoint = Point(r: r, c: c)
    }
}

enum Direction {
    case up
    case down
    case right
    case left
    
    func move(from p: Point) -> Point {
        switch self {
            case .up: return Point(r: p.r-1, c: p.c)
            case .down: return Point(r: p.r+1, c: p.c)
            case .right: return Point(r: p.r, c: p.c+1)
            case .left: return Point(r: p.r, c: p.c-1)
        }
    }
    func back(from p: Point) -> Point {
        switch self {
            case .up: return Point(r: p.r+1, c: p.c)
            case .down: return Point(r: p.r-1, c: p.c)
            case .right: return Point(r: p.r, c: p.c-1)
            case .left: return Point(r: p.r, c: p.c+1)
        }
    }
    
    static var all: [Direction] {
        return [.up, .down, .right, .left]
    }
}

func explore(tryCount: Int, red rPoint: Point, blue bPoint: Point, direction dir: Direction) {
    guard tryCount < 10 else { return }

    var movedRed = rPoint
    var movedBlue = bPoint
    
    while board[movedRed.r][movedRed.c] == "." {
        movedRed = dir.move(from: movedRed)
        
        // 이동 방향에 bPoint가 있었으면 hole에 도달하지 못했을 것이므로
        // 도달했으면 성공
        if movedRed == holePoint {
            break
        }
    }
    if board[movedRed.r][movedRed.c] == "#" {
        movedRed = dir.back(from: movedRed)
    }
    
    while board[movedBlue.r][movedBlue.c] == "." {
        movedBlue = dir.move(from: movedBlue)

        if movedBlue == holePoint {
            return
        }
    }
    if board[movedBlue.r][movedBlue.c] == "#" {
        movedBlue = dir.back(from: movedBlue)
    }
    
    if movedRed == holePoint {
        minimumTry = min(minimumTry, tryCount+1)
        return
    }
    
    // 두 구슬 모두 움직임이 없다면 return
    if movedBlue == bPoint, movedRed == rPoint {
        return
    }
    
    // 겹친다면,
    if movedRed == movedBlue {
        var rBack = true
        switch dir {
            case .up:
                rBack = rPoint.r > bPoint.r
            case .down:
                rBack = rPoint.r < bPoint.r
            case .right:
                rBack = rPoint.c < bPoint.c
            case .left:
                rBack = rPoint.c > bPoint.c
        }
        
        if rBack {
            movedRed = dir.back(from: movedRed)
        } else {
            movedBlue = dir.back(from: movedBlue)
        }
    }
    
    
    
    for nextDir in Direction.all {
        if dir == .up, nextDir == .down {
            continue
        } else if dir == .down, nextDir == .up {
            continue
        } else if dir == .right, nextDir == .left {
            continue
        } else if dir == .left, nextDir == .right {
            continue
        }
        explore(tryCount: tryCount+1, red: movedRed, blue: movedBlue, direction: nextDir)
    }
}

for dir in Direction.all {
    explore(tryCount: 0, red: redPoint, blue: bluePoint, direction: dir)
}

minimumTry == Int.max ? print(-1) : print(minimumTry)

 

 

배운점

아아 어렵네요 어려워... 이런 부분도 연습만이 살길인 것 같습니다.