[백준/C++/Graph] 16928 뱀과 사다리 게임

0. 풀이한 문제

뱀과 사다리 게임 / 골5 / 16928 / bfs

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

 

1. 테스트 케이스 분석

백준에 있는 예시는 너무 길고 많아서 간단하게 확인할 예제를 chat gpt에 물어보고 활용했다

 

gpt가 알려준 예제는

사다리 2->15 ,  5 -> 7

뱀 17 -> 3

이다

 

이동을 시작하기 전 초기 상태를 0번째 단계라고 하면

0번째 단계에서 시작 위치는 1이고 누적 거리 합은 0 이다

시작 위치는 백준에서 범위 값을 0이 아닌 1부터로 했기 때문에 1이고

최단 거리를 리턴해야하므로 누적 거리 합을 체크하는 부분이 필요해서

현재 위치와 누적 거리 합을 하나의 쌍으로 묶어서 생각했다

 

현재 위치인 1에서 이동할 수 있는 거리는

주사위 1~6까지 중 하나의 값을 더해서 나오는 값이므로 

2~7까지 이동 가능하다

 

큐에 이동할 수 있는 2~7을 넣어주어야 하는데

이때 누적 이동 거리는 주사위 한 번으로 이동한 것이니 1이다

 

큐에 삽입하려고 할 때 

2와 5 좌표에서는 사다리가 있어서 무조건 이동해야하니

최종 좌표는 15와 17이 되고

사다리를 통해 이동하는 거리는 카운트 되지 않으니 누적 이동 거리 합은 여전히 1이다

 

 

첫 이동을 끝낸 상태의 큐이다

큐에는 시작 위치 1에서 주사위로 이동할 수 있는 좌표로 이동한 후 

사다리가 있는 곳은 사다리 이동까지 한 후 

최종 좌표를 큐에 삽입한 상태이다

 

bfs로 탐색하는 것이므로 방문한 좌표는 

다시 방문하지 않기 위해 visited 배열을 true로 바꿔서

재방문하지 않도록 처리한다

 

큐에서 하나씩 꺼내서 이동할 수 있는 좌표를 더 탐색한다

일단 첫번째 요소인 (15, 1) 을 큐에서 pop할 것이다

 

(15, 1) 에서 주사위로 이동할 수 있는 좌표는 1~6을 더한 16~21이다

누적 거리 합이 1인 좌표에서 한 칸 더 이동하는 것이므로

16~21은 누적 거리 합이 2일 것이다

 

해당 범위에서 무조건 이동해야하는 뱀은 17 -> 3이 있으므로

17로 이동하는 좌표는 최종적으로 큐에 삽입될 때는 3이 될 것이다

 

큐에 이미 좌표가 3일 때 누적 거리 합이 1인 경우가 있지만

지금 추가하게 되는 것은 거리 합이 2인 경우로 다른 쌍이기 때문에

갱신하지 않고 추가한다

 

방문하게 되는 모든 인덱스는 또 true로 바꾸어 방문 처리한다

 

세 번째 단계에서는 다음 차례인 (3,1) 값을 꺼내서 같은 과정을 또 반복한다

반복하다가 현재 위치가 100일 때 누적 거리 합을 리턴하면 된다

 

2. 코드

코드는 인접 행렬과 인접 리스트 두 가지 방법으로 작성해서 

함수가 두 개이다

함수를 호출하는 두 가지 문장 중 하나만 주석처리하면

백준에서 정답 처리된다

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAX = 100;
int board[MAX + 1]; // 보드 (1번 칸부터 100번 칸까지)
// 각 인덱스 칸에서 뱀이나 사다리를 타고 이동할 칸을 저장
// 뱀이나 사다리로 연결된 칸이 없으면 0

// 인접 행렬
int bfs_matrix() {
    bool visited[MAX + 1]; // 방문 여부
    memset(visited, false, sizeof(visited));

    queue<pair<int, int>> q; // (현재 위치, 주사위 던진 횟수)
    q.push({1, 0});
    visited[1] = true;

    while (!q.empty()) {
        int current = q.front().first;
        int moves = q.front().second;
        q.pop();

        if (current == 100) {
            return moves;
        }

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

            if (next <= 100 && !visited[next]) {
                visited[next] = true;
                if (board[next] != 0) {
                    next = board[next];
                }
                q.push({next, moves + 1});
            }
        }
    }

    return -1; // 도달 불가능한 경우
}

// 인접 리스트
int bfs_list() {
    bool visited[MAX + 1]; // 방문 여부
    memset(visited, false, sizeof(visited));

    queue<pair<int, int>> q; // (현재 위치, 주사위 던진 횟수)
    q.push({1, 0});
    visited[1] = true;

    while (!q.empty()) {
        int current = q.front().first;
        int moves = q.front().second;
        q.pop();

        if (current == 100) {
            return moves;
        }

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

            if (next <= 100 && !visited[next]) {
                visited[next] = true;
                if (board[next] != 0) {
                    next = board[next];
                }
                q.push({next, moves + 1});
            }
        }
    }

    return -1; // 도달 불가능
}

int main() {
    int n, m;
    cin >> n >> m;

    // 보드 초기화
    memset(board, 0, sizeof(board));

    // 사다리와 뱀 정보 입력
    for (int i = 0; i < n + m; i++) {
        int start, end;
        cin >> start >> end;
        board[start] = end;
    }

    // 최소 주사위 던진 횟수 계산
    int result;

    result = bfs_matrix(); // 인접 행렬
    // result = bfs_list(); // 인접 리스트

    // 결과 출력
    cout << result << endl;

    return 0;
}