16928 뱀과 사다리 게임

16928 뱀과 사다리 게임 (c++)

문제

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

접근 방식

재귀, dp, 브루트포스

1. 사다리와 뱀을 저장하고
2. 첫번째 칸부터 진행하면서
   1. 사다리가 있다면 사다리를 타고 간 칸을 업데이트
   2. 뱀이 있다면 뱀을 타고 간 칸을 업데이트
   3. 둘 다 없다면 현재칸 앞의 6칸을 업데이트

문제 풀이

#include <iostream>
using namespace std;
int arr[101] = {};
int snake[101] = {};
int ladder[101] = {};

int N, M;

void Update(int pos, int cnt)
{
    if (pos > 100) return;
    if (pos == 1 && cnt) return;
    else if (arr[pos] != 0 && cnt >= arr[pos]) return;

    arr[pos] = cnt;
    if (ladder[pos]) Update(ladder[pos], cnt);
    else if (snake[pos]) Update(snake[pos], cnt);
    else
    {
        for (int i = 1; i <= 6; ++i)
        {
            Update(pos + i, cnt + 1);
        }
    }
}

int main()
{
    cin >> N >> M;

    while (N-- > 0)
    {
        int temp1, temp2;
        cin >> temp1 >> temp2;
        ladder[temp1] = temp2;
    }
    while (M-- > 0)
    {
        int temp1, temp2;
        cin >> temp1 >> temp2;
        snake[temp1] = temp2;
    }

    Update(1, 0);

    cout << arr[100] << endl;

    return 0;
}

다시 생각해볼 점

1. 재귀를 풀 때는 종료 조건을 명확히 해야한다.
   1. 1이 아닐때는 0이면 초기화가 안된것이므로 바로 입력, 0이 아니면 이미 다른 값으로 초기화가 된 것이므로 둘 중 최소값으로 업데이트해야한다.
   2. 1일 때는 0이상의 값이 들어오면 무시해야한다. (첫번째 칸과 다른 칸들의 차이가 여기서 나온다. 이걸 체크 안해서 틀렸음)
2. 적은 수는 브루트포스로 충분히 풀만하다. (1초에 1억번의 간단한 계산이 가능하다고 생각하자)