[BOJ] 16928 뱀과 사다리 게임 (Swift)

문제 링크

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

 

(미리보기가 왜 안될까 .. ㅜㅜ)

 

문제 접근

- 보드의 사이즈는 10 x 10, 각 보드판에는 1부터 100까지의 숫자가 적혀있다.

- i라는 위치에서 뱀과 사다리가 없다면, 갈 수 있는 곳은 i+1 부터 i+6 까지이다.

- 뱀 또는 사다리가 있다면, 무조건 이동해야 한다.

 

위 정보를 가지고 그래프 탐색을 이용해야겠다고 생각했다.

 

 

문제 풀이

보드의 사이즈가 고정이고, 특정 위치에서 갈 수 있는 위치를 모두 알 수 있기 때문에 탐색을 위한 배열을 이용한다.

 

배열 graph는 인덱스 0부터 100까지 총 101개이며, 각 요소로는 해당 인덱스(숫자)에서 이동할 수 있는 위치들을 저장한다.

예를 들어, 1번에서 갈 수 있는 위치는 2번부터 7번이므로 graph[1]에는 [7, 6, 5, 4, 3, 2]을 저장한다. 역순으로 저장하는 이유는 100까지 가장 최소로 이동하는 것이 목표이므로 더 먼 곳을 우선으로 두었다.

 

뱀과 사다리의 정보를 바탕으로 graph의 값을 업데이트한다. 배열 graph에서 뱀 또는 사다리의 출발점이 되는 위치에는 [4] 와 같이 값을 하나만 가진다.

 

위 graph 배열을 가지고 BFS로 탐색을 시작한다.

 

 

 

[BFS]

1. 먼저 queue를 생성하고 탐색의 시작점인 1을 넣는다.

2. queue의 가장 첫 번째 값을 꺼낸다. 이 값을 currentPos라 하겠다.

3. 배열 graph를 이용하여 currentPos에서 갈 수 있는 위치를 모두 확인한다. 여기서 확인한 위치를 nextPos라 하겠다.

    3.1  `nextPos`를 방문한 적이 없거나
    3.2 `nextPos`까지의 최소 주사위 횟수가 `currentPos`까지의 최소 주사위 횟수 + 1 보다 클 경우 
    -> `nextPos`의 최소 주사위 횟수를 업데이트하고 `queue`에 `nextPos`를 넣는다. 
    -> 이때 `currentPos`가 뱀 또는 사다리가 있는 위치일 경우, `nextPos`의 최소 주사위 횟수는 `currentPos`의 최소 주사위 횟수와 같다. 

4. queue에 있는 값을 모두 탐색할때까지 2,3번을 반복한다.

 

 

중요한 점

- 한 위치를 출발지로 하는 뱀 또는 사다리는 무조건 1개 이하이지만, 한 위치를 도착지로 하는 것에는 제한이 없다.

  즉, 10이라는 값을 도착지로 하는 뱀 또는 사다리는 여러개일 수 있다.

- 최소 주사위 횟수를 업데이트 할 때는 이미 저장된 값보다 작은지 꼭 확인을 해야한다.

  뱀과 사다리를 탈 때 주사위 횟수를 추가하지 않는다고 해서 nextPos에 currentPos의 주사위 횟수를 그대로 저장하면 안된다.

 

이것 때문에 몇 번 틀렸다 ..

 

 

도움이 됐던 테스트케이스

2 1
7 94
8 94
55 54

answer: 2

 

 

코드

import Foundation

let nm = readLine()!.split(separator: " ").map{Int($0)!}
var graph = (0...100).map { i in Array(stride(from: min(i+6, 100), through: i+1, by: -1))}
var price: [Int] = Array(repeating: 0, count: 101)
for _ in 0..<nm[0]+nm[1] {
    let input = readLine()!.split(separator: " ").map{Int($0)!}
    graph[input[0]] = [input[1]]
}

func bfs() {
    var queue = [1]
    var index = 0

    while index < queue.count {
        let current = queue[index]
        index += 1

        var check: Int = 1
        // 뱀 or 사다리
        if graph[current].count == 1 && current != 99 {
            check = 0
        }

        for next in graph[current] {
            // 1. 다음 목적지에 방문한 적이 없거나
            // 2. 다음 목적지의 최소 이동 횟수가 현재보다 클 때 (업데이트 필요할 때)
            if price[next] == 0 || price[next] > price[current]+check {
                price[next] = price[current]+check
                queue.append(next)
            }
        }
    }
}

bfs()

print(price[100])