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

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

16928번: 뱀과 사다리 게임

 

 

[ 문제풀이 ]

 

bfs를 활용하여 문제를 풀었습니다.

 

1. 각 칸을 자신으로 초기화합니다.

 

2. 사다리와 뱀을 입력받습니다.

 

3. bfs를 활용하여 100번 칸에 도착하면 답을 출력하고 종료합니다.

 

위의 3번 과정을 진행할 때 한 번의 과정 동안 6번의 반복을 하면서 방문 여부를 체크해주고, 방문하지 않았다면 queue에 넣어 다음 과정을 진행해 줍니다.

 

[ 소스 코드 ]

#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[101];        //각 칸의 이동 위치
int visited[101];    //각 칸의 방문 여부
 
struct node {
    int cur;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= 100; i++) {    //각 칸의 이동 위치를 자신으로 초기화
        arr[i] = i;
    }
 
    for (int i = 0; i < N; i++) {    //사다리 입력
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a] = b;
    }
 
    for (int i = 0; i < M; i++) {    //뱀 입력
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr[a] = b;
    }
 
    queue<node> q;
    q.push({ 1, 0 });
 
    while (1)
    {
        int cur = q.front().cur;
        int cnt = q.front().cnt;
        q.pop();
 
        if (cur == 100) {    //100번 칸에 도착하면 cnt 출력 후 종료
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[cur] == 1) continue;
        visited[cur] = 1;
 
        for (int i = 1; i <= 6; i++) {
            int next = arr[cur + i];    //이동할 칸
            if (visited[next] != 1) {
                q.push({ next, cnt + 1 });
            }
        }
    }
}