알고리즘 풀이/백준(Boj)
백준(BOJ) 16928번 뱀과 사다리 게임
100win10
2019. 11. 1. 01:50
문제 : https://www.acmicpc.net/problem/16928
16928번: 뱀과 사다리 게임
첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다. 다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다. 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸
www.acmicpc.net
풀이 :
최소 몇 번의 주사위를 굴렸는지 구해야 하므로 BFS로 해결하자. 큐에 시작점인 1부터 넣고 주사위의 경우의 수인 1부
터 6만큼 각각 더한 수를 q에 넣을지 말지 결정한다. 이때 사다리나 뱀이 있는 위치라면 그 위치로 이동해주어야 한다.
코드 ( C++ )
