반응형
https://www.acmicpc.net/problem/16928
16928번: 뱀과 사다리 게임
첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으
www.acmicpc.net
소스코드
풀이
★ 주사위를 던지면서 모든 경우의 수를 확인해야 하는 완전탐색 문제입니다 ! 이 때 사다리와 뱀의 정보를 이용하는 것이 중요합니다. 뱀은 높은 칸에서 낮은 칸으로 이동하기에 100으로 가기에는 필요없다고 생각할 수도 있는데,
사다리 (10 - 50), 뱀 (50-28), 사다리 (28 - 99)처럼 뱀을 이용해서도 100으로 빠르게 이동할 수 있습니다 !
★ 위의 원리를 파악했다면 visited 배열을 통해 이동한 칸들을 체크하여 중복으로 방문하지 않도록 합니다. 또한 결과값으로 주사위를 던진 횟수를 출력해야 하기 때문에 queue에 추가할 때마다 변수 y를 1씩 증가시켜 주사위 던진 횟수를 카운팅 해줍니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 8979번: 올림픽 (Python) (0) | 2023.10.20 |
|---|---|
| [백준 알고리즘] 18870번: 좌표 압축 (Python) (0) | 2023.10.20 |
| [백준 알고리즘] 13549번: 숨바꼭질 3 (Python, BFS) (0) | 2023.10.18 |
| [백준 알고리즘] 2346번: 풍선 터뜨리기 (Python) (0) | 2023.10.18 |
| [백준 알고리즘] 2776번: 암기왕 (Python) (0) | 2023.10.17 |