[백준/Swift] 16928번: 뱀과 사다리 게임

 

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

16928번: 뱀과 사다리 게임

 

 

보드판은 함정. 좌표를 사용할 일이 없다.

어떤 칸 i에서 이동할 수 있는 곳 → i+1, i+2, i+3, i+4, i+5, i+6, 뱀, 사다리로 이동

사다리와 뱀의 반대로 이동은 불가

100번 칸에 도착하기 위해 굴려야 할 주사위의 최소 횟수 구하기

BFS, 좌표칸을 vertex로.

 

✅ 사다리나 뱀의 시작점을 만나면 무조건 타고 이동해야 됨.

✅ 사다리나 뱀을 타고 이동하면 카운팅 하지 않는다! 주사위 굴린 것이 아니니까

 

헷갈렸던 부분

방문한 곳을 재방문해도 되는가?

→ 사실 당연히 안 되는 거였음. 재방문해도 이동하는 길은 똑같기 때문!

 

 

1에서 시작해서 100에 도착해야 한다. 각 이동한 칸을 정점(vertex)으로 두고 BFS 탐색을 진행했다.

Queue에 현재 위치와 주사위를 굴린 횟수를 Tuple로 저장했다.

주사위를 굴리면 1~6의 경우가 나오는데, 이 값으로 이동한 next 위치가 100이라면

지금까지의 주사위 횟수(cnt)+1(다음 칸으로 간 횟수)를 출력하고 끝낸다.

만약 100이 아직 안되었다면, next에 사다리 혹은 뱀이 있는지 체크한다. 있다면 무조건 타고 이동해야 한다.

이동 시, 주사위를 굴리지 않으므로 next의 값만 변경해 준다.

여기서 꼭 중복을 체크해줘야 한다. 위에도 적었지만 방문한 곳을 재방문한다고 달라지는 게 없고 그저 cnt 횟수만 늘어난다.

방문한 곳이 아니라면 queue에 넣고 방문 체크를 한 뒤 계속 진행한다.

 

 

import Foundation

/*
 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?
 주사위의 각 면에는 1~6까지의 수가 적혀있다.
 10x10 보드판. 1부터 100까지 수가 하나씩 순서대로 적혀있다.
 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4면 i+4 칸으로 이동
 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸이면 뱀을 따라거 내려간다.
 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아짐.
 게임의 목표는 1번에서 시작해 100번 칸에 도착.
 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값 구하기
 */

//input
let nm = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (n, m) = (nm[0], nm[1])
var ladderNsnake = [Int](repeating: 0, count: 102) //겹치지 않기 때문에 ㄱㅊ
var check = [Bool](repeating: false, count: 102)
for _ in 0..<n+m {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    ladderNsnake[input[0]] = input[1]
}

//1에서 시작해서 100에 도달해야됨
func BFS() {
    var queue = [(1, 0)] //현재 위치, 카운트(주사위 굴린 횟수)
    var front = 0
    
    while queue.count > front {
        let (x, cnt) = (queue[front].0, queue[front].1)
        front += 1
        
        //주사위 굴린 경우
        for i in 1...6 {
            var next = x + i
            if next == 100 { //도착했기 때문에 끝내기!
                print(cnt + 1)
                return
            } else if next < 100 {
                //사다리 혹은 뱀을 위치 1에서는 체크하지 않은 것은, 1과 100에선 뱀과 사다리가 없기 때문
                if ladderNsnake[next] != 0 {  //이동한 곳에 사다리 혹은 뱀이 있다면 이동! (무조건 이동)
                    next = ladderNsnake[next] //사다리로 이동하면 카운팅 없음, 위치만 변경
                }
                if !check[next] {             //방문한 곳이 아니라면 방문! (재방문 없음)
                    queue.append((next, cnt + 1))
                    check[next] = true
                }
            }
        }
    }
}
BFS()