16928번: 뱀과 사다리 게임

Memo

continue.......

찬호님의 도움을 받았습니당..

input

사다리의 개수와 뱀의 개수를 입력받는다. 이후 사다리와 뱀이 시작위치와 도착위치의 key-value 쌍으로 들어오게 된다. 사다리와 뱀의 경우 중복된 키가 없기때문에 입력, 탐색에서 효율적인 map을 활용했다. 또한 사다리, 뱀을 따로 만들 필요가 없이 하나의 자료구조를 활용하면 되기 때문에 두 경우 모두 하나의 map을 활용해서 넣어주었다.

void input()
{
	int from, to;

	std::cin >> cnt_ladder >> cnt_snake;
	visited.resize(101);
	for (int i = 0 ; i < cnt_ladder + cnt_snake ; ++i)
	{
		std::cin >> from >> to;
		ladder_snake.insert(std::pair<int, int>(from, to));
	}
}

solution

bfs를 활용해서 가장 먼저 100번째 칸에 도착한 경우가 가장 적은 횟수의 주사위를 굴린 것이라고 생각했다.

for (int i = 1 ; i <= 6 ; i++)
		{
			int next = val + i;
			if (!visited[next] && !visited[100])
			{
				visited[next] = visited[val] + 1;
				que.push(next);
			}
		}

주사위를 굴려서 나올수 있는 값인 1 ~ 6 까지를 for문을 사용해서 반복시킨다.

너비우선 탐색이기 때문에 우선 갈 수 있는 곳 순서대로 queue에 값을 push한다.

예를들어 1에서는 2, 3, 4 ,5, 6, 7을 갈 수 있기 때문에 visited[2 - 7]에는 visited[1] + 1값이 들어가게 된다.

하지만 사다리와 뱀을 활용해 우리는 다른 위치로 이동할 수가 있다. 그래서 우리는 해당 인덱스에서 한번 더 조건 체크를 해주어야 한다. map에 key값이 존재한다면 ladder_snake[next] 값이 0이상으로 나올 것이기 때문에 해당 조건을 체크해준다.