백준 16928번(뱀과 사다리 게임) C++ 풀이

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

int map1[101] = {0};
int visited[101] = {0};
int ans = 0;
void bfs(int start)
{
    visited[start] = 1;
    queue<int> q;
    q.push(start);

    while (!q.empty())
    {

        int front = q.front();
        q.pop();

        for (int i = 1; i <= 6; i++)
        {
            if (front + i == 100)
            {

                cout << visited[front];

                return;
            }
            if (front + i < 100)
            {
                if (visited[front + i] == 0)
                {
                    if (map1[front + i] != 0)
                    {
                        if (visited[map1[front + i]] == 0)
                        {

                            q.push(map1[front + i]);
                            visited[front + i] = visited[front] + 1;
                            visited[map1[front + i]] = visited[front] + 1;
                        }
                    }
                    else
                    {

                        q.push(front + i);
                        visited[front + i] = visited[front] + 1;
                    }
                }
            }
        }
    }
}

int main()
{
    int trail, snake;
    cin >> trail >> snake;

    for (int i = 0; i < trail; i++)
    {
        int a, b;
        cin >> a >> b;
        map1[a] = b;
    }
    for (int i = 0; i < snake; i++)
    {
        int a, b;
        cin >> a >> b;
        map1[a] = b;
    }
    bfs(1);
}

bfs를 이용해서 손쉽게 문제를 해결할 수 있었다. 골드치고는 쉬운 문제였는데,

 if (visited[front + i] == 0)
                {
                    if (map1[front + i] != 0)
                    {
                        if (visited[map1[front + i]] == 0)
                        {

                            q.push(map1[front + i]);
                            visited[front + i] = visited[front] + 1;
                            visited[map1[front + i]] = visited[front] + 1;
                        }
                    }

이런 식으로, 내가 다음 주사위를 굴려서 갈 곳에 뱀이나 사다리가 있을 경우, 위 코드처럼 2개의 visited를 체크해주는 식으로 문제를 해결하였고,

else
{
 q.push(front + i);
   visited[front + i] = visited[front] + 1;
 }
 

그게 아닐 경우에는, 그냥 평범하게 주사위를 이용한 bfs 계산을 해주었다.