백준 16928번 뱀과 사다리 게임

🔒[문제 url]

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

🔑알고리즘

전형적인 1차원 BFS 문제이다.

• 뱀과 사다리를 만났을 경우 어떻게 처리하는가?
  • $x$에서 $y$로 가는 뱀 또는 사다리를 만난 경우,
    방문 처리를 하는 지점은 $x$가 아닌 $y$이다.
    같은 원리이기 때문에, 뱀과 사다리를 분리해 생각할 필요는 없다.
    
    이외 로직은 일반 BFS와 동일하다.

🐾부분 코드

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= 100; i++)
    {
        visited[i] = -1;
        item[i] = i;
    }
    for (int i = 0; i < n + m; i++)
    {
        int u, v; cin >> u >> v;
        item[u] = v;
    }
}

<입력 함수>
뱀과 사다리를 굳이 분리하지 않고 하나로 입력받는다.

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

    while (!q.empty())
    {
        int now = q.front();
        if (now == 100) break;
        q.pop();

        for (int i = 1; i <= 6; i++)
        {
            int next = now + i;
            if (next > 100) break;
            next = item[next];

            if (visited[next] == -1)
            {
            	// 경로 길이 표기
				visited[next] = visited[now] + 1;
				q.push(next);
            }
        }
    }
}

<BFS 함수>
뱀이나 사다리를 만난 경우, 그 끝 지점에 가므로 방문처리또한 끝 지점에 한다.
주사위이므로 for문의 범위는 $1 \leq i \leq 6$ 이고, 범위에 주의한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
// 자료 구조
#include <queue>
using namespace std;

int n, m;
int item[101];
int visited[101];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= 100; i++)
    {
        visited[i] = -1;
        item[i] = i;
    }
    for (int i = 0; i < n + m; i++)
    {
        int u, v; cin >> u >> v;
        item[u] = v;
    }
}

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

    while (!q.empty())
    {
        int now = q.front();
        if (now == 100) break;
        q.pop();

        for (int i = 1; i <= 6; i++)
        {
            int next = now + i;
            if (next > 100) break;
            next = item[next];

            if (visited[next] == -1)
            {
            	// 경로 길이 표기
				visited[next] = visited[now] + 1;
				q.push(next);
            }
        }
    }
}

void SOLVE()
{
    BFS();
    cout << visited[100];
}



int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

1. 뱀과 사다리를 나누어 생각할 필요없다는 것(나눠도 되긴하지만)
2. 뱀이나 사다리를 만날 경우 방문하는 지점은 그 끝 지점이라는 것
   두 가지만 캐치하면 간결해지는 BFS이었으나, 2번을 놓쳐 조금 헤맸던 문제.
   그러나 데이터를 쌓을 수 있어 가치있는 시간이었다.