16928번 - 뱀과 사다리 게임 c++

문제설명

 

1번칸 -> 100번칸을 도달하기까지의 주사위 돌리는 횟수의 최소값을 구하는 문제

 

다른 대표적인 그래프탐색 문제처럼 상하좌우로 이동하는 것이 아닌, (+1, +2, +3, +4, +5, +6)로만 이동하는 것이기에 1차원 배열을 사용

 

이 문제에서 가장 중요한 포인트이자, 저를 포함한 많은 분들이 간과했던 문제는

1. 뱀과 사다리가 있는 칸에 주사위 이동으로 갈지 vs 뱀/사다리를 탈지 선택하면 안되는 것
2. 뱀을 타는 것이 더 빠른 경우

 

1번은 탐색하면서 뱀과 사다리가 있는 칸에 도착한다면 선택의 여지없이 뱀이나 사다리를 무조건 타서 이동시켜야 합니다.

if(ladder_snake[next_x] > 0 && ladder_snake[next_x] < next_x)
    next_x = ladder_snake[next_x];

ladder_snake[]: 뱀과 사다리 위치 정보가 저장되어 있는 배열

next_x: 탐색할 칸

x: 현재 위치

 

ladder_snake[next_x] > 0은 탐색하는 곳에 사다리 혹은 뱀이 존재하냐는 뜻이고

ladder_snake[next_x] < next_x는 뱀을 탔을 때 입니다.

(뱀을 탔을 때만 고려한 이유는 뱀으로 이동한 칸은 이미 거리 정보가 저장이 되어있기 때문에 다시 탐색하게끔 했습니다.) 

 

 

 

 

2번에 대한 예시 입니다.

//반례
2 1
2 60
35 98
65 30

//answer : 4

뱀을 타지 않도록 설계되어있다면

1) 1 -> 7

2) 7 -> 13

3) 13 -> 19

4) 19 -> 25

5) 25 -> 31

6) 31 -> 35(98)

7) 98 -> 100 

--------------------

7번만에 도착할 것 입니다.

 

따라서 다익스트라 알고리즘처럼

최단 경로 횟수를 저장시켜놓고 더 작은 횟수로 도달할 수 있다면 그 횟수로 업데이트를 해줘야 합니다.

 

 

 

 

 

 

#include<iostream>
#include<queue>

std::queue<int> q;
int game[101];
int ladder_snake[101] = {0,};
const int INF = 100000000;

int BFS(int x)
{
    q.push(x);
	while(!q.empty())
	{
		int dice[] = {1, 2, 3, 4, 5, 6};
        x = q.front();
	    q.pop();
		
		for(int i=0; i<6; i++)
		{
			int next_x = x + dice[i];
			if(next_x > 100)
				continue;
			if(ladder_snake[next_x] > 0 && ladder_snake[next_x] < next_x)
			    next_x = ladder_snake[next_x];
			if(game[x] + 1 < game[next_x])
			{
				game[next_x] = game[x] + 1;
			    q.push(next_x);
			}
			if(ladder_snake[next_x] > 0 && game[next_x] < game[ladder_snake[next_x]])
			{
				game[ladder_snake[next_x]] = game[next_x];
				q.push(ladder_snake[next_x]);
			}
		}
	}
	return game[100];
}


int main()
{
	int N, M;
	std::cin >> N >> M;
	
	for(int i=1; i<=100; i++)
	{
		game[i] = INF;
	}
	game[1] = 0;
	
	for(int i=1; i<=N+M; i++)
	{
		int x, y;
		std::cin >> x >> y;
		ladder_snake[x] = y;
	}
	std::cout << BFS(1) << std::endl;
}