/<> 백준 16928번 : 뱀과 사다리 게임 (C언어)

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

 

 

사다리와 뱀은 올라가고 내려가는 차이가 있을 뿐, 이동한다는 사실 자체는 같고 서로 같은 칸을 공유하지 않으므로 한 배열 안에 모두 저장해도 상관없습니다. 이를 통해 메모리를 아낄 수 있습니다.

 

문제 풀이 방식은 BFS입니다. 주사위의 수가 1부터 6까지 있으니 큐에 경우의 수를 모두 넣고 탐색하는 방식을 반복하면 됩니다. 이후 마지막 100번째 칸에 도착했을 때 굴린 주사위 횟수를 출력하면 됩니다. 주사위 횟수 또한 칸마다 몇 번째로 굴렸을 때 도착했는지 배열로 만들어 저장하면 연산이 편합니다.

 

 

<코드>

#include <stdio.h>
#include <string.h>

int jump[101];
int dice[101];

int queue[101];
int front = 0, rear = 0;

void push(int x) {
    queue[rear++] = x;
}

int pop() {
    return queue[front++];
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < n + m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        jump[u] = v;
    }

    memset(dice, -1, sizeof(dice)); // 방문 기록 초기화
    push(1); // 시작점(1번 칸) 큐에 삽입
    dice[1] = 0; // 시작점에서 주사위를 굴린 횟수는 0

    while (front != rear) {
        int x = pop();
        for (int i = 1; i <= 6; ++i) {
            int nx = x + i;
            if (nx > 100) continue;

            if (jump[nx] != 0) {
                nx = jump[nx];
            }
            
            if (dice[nx] == -1) {
                dice[nx] = dice[x] + 1;
                push(nx);
            }
        }
    }
    
    printf("%d\n", dice[100]);
    return 0;
}

 

 

처음 풀었을 땐 다음과 같은 이유로 계속 실패가 떴습니다.

 

1. 뱀과 사다리 배열을 따로 만듦

2. 주사위 굴린 횟수 배열을 만들지 않았음

3. 큐 관련 함수를 따로 만들지 않고 직접 코드를 입력함

 

1번과 3번은 그렇다 쳐도, 2번에서 전 queue와 dice 배열을 합친, 이차원 배열을 통해 문제를 풀었습니다. 확실히 스스로가 푸는 도중에 헷갈릴 만했습니다. 따로 구분해서 알기 쉽게 풀어야겠습니다.