백준 16928번: 뱀과 사다리 게임

문제

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

16928번: 뱀과 사다리 게임

 

---

풀이

각 면에 1부터 6까지 수가 하나씩 적혀있는 정육면체 주사위를 사용하며 총 100개의 칸으로 나누어져 있는 보드판이 있을 때 플레이어는 주사위를 굴려 나온 수만큼 이동해야 합니다.

이때 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없으며 사다리가 있는 칸에 도착하면 사다리를 따라 위로 올라가고 뱀이 있는 칸에 도착하면 뱀을 따라서 내려가게 됩니다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것일 때 주사위를 굴려야 하는 횟수의 최솟값을 구하는 문제입니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;

class point {
    int x, cnt;

    public point(int x, int cnt) {
        this.x = x;
        this.cnt = cnt;
    }
}

public class Main {

    static int n, m;
    static int[] arr;
    static boolean[] visited;

    public static void bfs() {
        Queue<point> queue = new LinkedList<>();
        queue.offer(new point(1, 0));
        visited[1] = true;
        while (!queue.isEmpty()) {
            point p = queue.poll();
            if (p.x == 100) { // (1)
                System.out.println(p.cnt);
                return;
            }
            for (int i = p.x + 6; i > p.x; i--) { // (2)
                if (i <= 100 && !visited[i]) {
                    if (arr[i] != 0) { // (3)
                        if (!visited[arr[i]]) {
                            queue.offer(new point(arr[i], p.cnt + 1));
                            visited[arr[i]] = true;
                        }
                    } else { // (4)
                        queue.offer(new point(i, p.cnt + 1));
                        visited[i] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[101];
        visited = new boolean[101];
        for (int i = 0; i < n + m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[x] = y;
        }
        bfs();
    }
}

정수 배열 arr는 해당 칸에 뱀이나 사다리가 있는 경우 어디로 이동하는지를 나타냅니다. 아무것도 없다면 보드판에 0번 칸이 없으므로 arr[해당 칸]은 0으로 지정했습니다. 모든 입력이 끝나면 bfs 함수로 들어갑니다.

 

bfs 함수 내부에 있는 큐에는 해당 칸의 위치와 해당 칸까지 이동하는데 굴린 주사위의 최소 횟수가 들어있는 point 클래스가 들어가며 1번 칸부터 시작하고 주사위를 0번 굴리므로 (1, 0)을 삽입하고 visited[1]을 true로 초기화합니다.

이후 큐에서 poll한 값을 p라고 했을 때 큐가 비어있지 않을 때까지 아래의 과정을 반복합니다.

 

(1) p.x가 100인지 여부를 확인합니다.

맞다면 게임의 목표를 달성한 것이므로 p.cnt를 출력한 뒤에 return하여 프로그램을 종료합니다.

 

(2) 주사위를 굴리는 모든 경우의 수를 i를 포함한 for문으로 표현합니다.

주사위에는 1부터 6까지의 수가 적혀있기 때문에 p.x + 6부터 p.x + 1까지 반복하는데 이때 i가 100을 넘어가면 이동할 수 없고 i번 칸을 방문한 적이 있다면 i.cnt의 값은 p.cnt + 1보다 무조건 작거나 같기 때문에 넘어갑니다.

 

(3) arr[i]가 0인지 확인하여 해당 칸에 뱀 또는 사다리가 있는지 확인합니다.

뱀 또는 사다리가 있다면 무조건 해당 칸으로 이동해야하기 때문에 arr[i]에 방문한 적이 있는지 확인합니다.

방문한 적이 없다면 큐에 (arr[i], p.cnt + 1)을 삽입하고 visited[arr[i]]를 true로 초기화합니다.

 

(4) 뱀 또는 사다리가 없다면 큐에 (i, p.cnt + 1)을 삽입하고 visited[i]를 true로 초기화합니다.

이때 i번칸의 방문 여부는 이미 위(2)에서 확인했기 때문에 따로 확인하지 않습니다.

C언어

#include <stdio.h>
#include <stdlib.h>
int n, m, arr[101], cnt[101], visited[101];
typedef struct node {
	int data;
	struct node* next;
} node;
typedef struct Queue {
	node* front;
	node* rear;
	int count;
} Queue;
void initQueue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
void push(Queue* queue, int data) {
	node* now = (node*)malloc(sizeof(node));
	now->data = data;
	now->next = NULL;
	if (queue->count == 0) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
int pop(Queue* queue) {
	int re;
	node* now;
	if (queue->count == 0) {
		return -1;
	}
	now = queue->front;
	re = now->data;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
void bfs() {
	Queue queue;
	initQueue(&queue);
	push(&queue, 1);
	visited[1] = 1;
	while (!empty(&queue)) {
		int p = pop(&queue);
		if (p == 100) {
			printf("%d", cnt[100]);
			return;
		}
		for (int i = p + 6; i > p; i--) {
			if (i <= 100 && !visited[i]) {
				if (arr[i] != 0) {
					if (!visited[arr[i]]) {
						push(&queue, arr[i]);
						visited[arr[i]] = 1;
						cnt[arr[i]] = cnt[p] + 1;
					}
				}
				else {
					push(&queue, i);
					visited[i] = 1;
					cnt[i] = cnt[p] + 1;
				}
			}
		}
	}
}
main() {
	scanf("%d %d ", &n, &m);
	for (int i = 0; i < n + m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		arr[x] = y;
	}
	bfs();
}

자바를 이용한 풀이와 동일합니다. struct point는 따로 구현하지 않고 정수 배열 cnt를 이용하여 해당 칸까지 이동하는데 굴린 주사위의 최소 횟수를 표현했습니다.

---

결론

문제에는 10 x 10 크기의 보드판이라고 했지만 2차원 배열로 이를 표현할 필요가 없었던 문제였습니다. 이처럼 문제의 내용에만 너무 집착하지 않고 더 유연하게 사고하는 법을 배울 수 있는 시간이었던 것 같습니다.