[BOJ] 16928번 | 뱀과 사다리 게임 (C++)

🔗문제 보러가기

16928번: 뱀과 사다리 게임

 

 

🧑‍💻풀이 과정

 

BFS로 쉽게 풀 수 있는 문제인데, 저는 사다리나 뱀을 타고 간 보드칸을 방문 처리해주질 않아, 엉뚱한 답이 나왔습니다. 이걸 빨리 알아채지 못해서 시간을 좀 허비했네요. 아무튼, 제가 푼 풀이 과정은 다음과 같습니다.

 

1. 뱀이나 사다리 정보를 가지고 있는 vector<int> teleports(100 + 1)을 준비한다.
   • teleports[i] = 0   👉🏻 뱀이나 사다리가 없음을 의미
   • teleports[i] != 0  👉🏻 뱀이나 사다리를 타고 갈 다음 인덱스
2. 주사위를 굴린 횟수 정보를 가지고 있는 vector<int> diceCounts(100 + 1)을 준비한다.
3. 1번 위치부터 BFS 탐색을 시작한다.
   • 현재 위치(current)로부터 1 ~ 6을 더한 다음 위치 값(next)을 얻는다.
     • 보드게임 칸 범위를 넘어가거나 이미 방문(diceCounts[next] != 0)한 경우, continue
     • next == 100이라면, diceCounts[current] + 1을 리턴
     • 뱀이나 사다리가 있는 경우(teleports[next] != 0), next를 갱신
     • 뱀이나 사다리를 타고 간 곳이 이미 방문한 곳(diceCounts[next] != 0)인 경우, continue
     • diceCounts[next] = diceCounts[current] + 1을 하고, 큐에 next 삽입

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

const int BOARD_SIZE = 100;

int BFS(vector<int>& teleports, vector<int>& diceCounts) {
    queue<int> indexes;
    indexes.push(1);

    while (!indexes.empty()) {
        int current = indexes.front();
        indexes.pop();

        for (int i = 1; i <= 6; i++) {
            int next = current + i;

            if (next > BOARD_SIZE or diceCounts[next] != 0)
                continue;
            
            if (next == BOARD_SIZE)
                return diceCounts[current] + 1;

            while (teleports[next] != 0)
                next = teleports[next];

            if (diceCounts[next] != 0)
                continue;

            diceCounts[next] = diceCounts[current] + 1;
            indexes.emplace(next);
        }
    }

    return 0;
}


void AddTeleportInformations(vector<int>& next, int N) {
    int from, to;

    for (int i = 0; i < N; i++) {
        cin >> from >> to;
        next[from] = to;
    }
}

int main() {
    FAST_IO

    // 1. 초기화
    vector<int> teleports(BOARD_SIZE + 1, 0);
    vector<int> diceCounts(BOARD_SIZE + 1, 0);

    // 2. 사다리랑 뱀 요소 추가
    int ladderCount, snakeCount;
    cin >> ladderCount >> snakeCount;

    AddTeleportInformations(teleports, ladderCount);
    AddTeleportInformations(teleports, snakeCount);

    // 3. BFS 탐색 시작
    int answer = BFS(teleports, diceCounts);
    cout << answer;
    return 0;
}