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

🌘 문제

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

 

🌗 풀이

[BFS]

흔한 bfs문제이다

 

한칸에 사다리와 뱀이 동시에 있는 경우는 없기 때문에

board하나로 뱀와 사다리를 통한 이동을 확인할 수 있다

board[시작위치]=이동위치

 

🌖 코드

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

int main()
{
    // INPUT
    int ladderNum, snakeNum;
    cin >> ladderNum >> snakeNum;

    vector<int> board(101, 0);

    int from, to;
    for (int i = 0; i < ladderNum; i++) 
    {
        cin >> from >> to;
        board[from] = to;
    }
    for (int i = 0; i < snakeNum; i++) 
    {
        cin >> from >> to;
        board[from] = to;
    }

    vector<int> visited(101, 0);
    queue<pair<int, int>>q;//nowPosition, count


    //CHECK
    q.push({ 1,0 });
    visited[1] = 1;

    while (!q.empty())
    {
        int nowPos = q.front().first;
        int count = q.front().second;
        q.pop();

        if (nowPos == 100) { cout << count; break; }

        for (int i = 1; i <= 6; i++)
        {
            int nextPos = nowPos + i;
            if (nextPos > 100)continue;
            if (board[nextPos] != 0) { nextPos = board[nextPos]; }

            if (visited[nextPos] == 1)continue;
            visited[nextPos] = 1;
            q.push({ nextPos,count + 1 });
        }
    }

    return 0;
}