백준 16928번 [뱀과 사다리 게임](C++) -yes6686- 티스토리

백준 문제 풀이: 16928 [뱀과 사다리 게임]

---

문제 링크: https://www.acmicpc.net/problem/16928

문제 설명:

100칸으로 이루어진 게임판에서 뱀과 사다리를 이용하여 1번 칸에서 100번 칸으로 이동하는 최소 횟수를 구하는 문제입니다. 주사위를 던져 나온 숫자만큼 이동할 수 있으며, 사다리를 타면 더 높은 칸으로 이동하고, 뱀을 만나면 더 낮은 칸으로 이동합니다.

입력:

• 첫 줄에 사다리의 수 n과 뱀의 수 m이 주어집니다. (1 ≤ n, m ≤ 15)
• 다음 n개의 줄에 사다리의 시작점과 끝점이 주어집니다.
• 다음 m개의 줄에 뱀의 시작점과 끝점이 주어집니다.

출력:

• 1번 칸에서 100번 칸으로 가는 데 필요한 최소 이동 횟수를 출력합니다.

예시:

입력:
3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17

출력:
3

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int visited[101]; // 방문 여부
int moves[101];   // 각 칸에 도달하는 최소 횟수
int board[101];   // 뱀과 사다리를 처리한 보드 상태

void bfs() {
    queue<int> q;
    q.push(1);
    visited[1] = 1;
    moves[1] = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

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

            if (next > 100) continue;

            next = board[next]; // 사다리나 뱀이 있으면 이동
            if (!visited[next]) {
                visited[next] = 1;
                moves[next] = moves[cur] + 1;
                q.push(next);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= 100; i++) {
        board[i] = i; // 기본적으로 보드의 값은 자기 자신
    }

    for (int i = 0; i < n; i++) {
        int start, end;
        cin >> start >> end;
        board[start] = end; // 사다리
    }

    for (int i = 0; i < m; i++) {
        int start, end;
        cin >> start >> end;
        board[start] = end; // 뱀
    }

    bfs();

    cout << moves[100] << '\n'; // 100번 칸까지의 최소 이동 횟수 출력
    return 0;
}

---

코드 설명

이 코드는 BFS를 활용하여 최소 이동 횟수를 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘: BFS는 최단 경로를 찾는 데 적합합니다. 큐를 사용하여 각 칸에서 주사위로 이동 가능한 모든 경우를 탐색합니다.
• 구현 세부사항:
  • board[i]: 사다리나 뱀에 의해 이동할 수 있는 칸을 저장합니다.
  • visited[i]: 이미 방문한 칸을 다시 방문하지 않도록 처리합니다.
  • moves[i]: 각 칸에 도달하는 최소 횟수를 저장합니다.
• 시간 복잡도 분석:
  • BFS의 탐색 범위는 최대 100개의 칸이며, 각 칸에서 최대 6개의 경우를 탐색합니다.
  • 총 시간 복잡도: O(100 * 6) = O(600)

---

결과

코드는 1번 칸에서 100번 칸까지 가는 최소 이동 횟수를 정확히 계산합니다. BFS를 사용하여 모든 경우를 탐색하므로 정확하고 효율적으로 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!