Search
Duplicate
🍋

뱀과 사다리 게임

주차
14
문제번호
16928
언어
C++
티어
실버
유형
BFS
nj_Blog
nj_상태
이해도
풀이
풀이 O
사람
이해도 2
13 more properties

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)); } }
C++
복사

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); } }
C++
복사
주사위를 굴려서 나올수 있는 값인 1 ~ 6 까지를 for문을 사용해서 반복시킨다.
너비우선 탐색이기 때문에 우선 갈 수 있는 곳 순서대로 queue에 값을 push한다.
예를들어 1에서는 2, 3, 4 ,5, 6, 7을 갈 수 있기 때문에 visited[2 - 7]에는 visited[1] + 1값이 들어가게 된다.
하지만 사다리와 뱀을 활용해 우리는 다른 위치로 이동할 수가 있다. 그래서 우리는 해당 인덱스에서 한번 더 조건 체크를 해주어야 한다. map에 key값이 존재한다면 ladder_snake[next] 값이 0이상으로 나올 것이기 때문에 해당 조건을 체크해준다.
이후 사다리 혹은 뱀으로 이동하는 다음 좌표를 변수에 담아두고 해당 좌표에 대해 다시한번 방문체크를 진행한다. 만약 방문했던 좌표가아니라면 방문체크를 한 후 queue에 push한다.
if (ladder_snake[next] > 0) { int mv_next = ladder_snake[next]; if (!visited[mv_next]) { visited[mv_next] = visited[next]; que.push(mv_next); } continue; }
C++
복사
뱀, 사다리로 이동한 좌표를 push하게 되면 이전 좌표(사다리를 타기 전 좌표)는 push를 하게 되면 예외가 발생한다. 따라서 continue를 통해 다음 push를 스킵해주어야 한다. 하지만 아직 예외케이스를 찾진 못했다..

output

visited[100]에 주사위를 굴린 횟수가 저장되어 있기 때문에 해당 값을 출력한다. 하지만 visited[1]의 값을 1로 시작하였기 때문에 최종 출력에서는 1을 빼주어야 원하는 값을 찾을 수 있다.

Code

제출 날짜

@4/3/2021

메모리

2024 KB

시간

0 ms
#include <iostream> #include <vector> #include <queue> #include <map> int cnt_ladder, cnt_snake; std::map<int, int> ladder_snake; std::queue<int> que; std::vector<int> visited; void output() { std::cout << visited[100] - 1; } void bfs() { que.push(1); visited[1] = 1; while (!que.empty()) { int val = que.front(); que.pop(); for (int i = 1 ; i <= 6 ; i++) { int next = val + i; if (!visited[next] && !visited[100]) { visited[next] = visited[val] + 1; if (ladder_snake[next] > 0) { int mv_next = ladder_snake[next]; if (!visited[mv_next]) { visited[mv_next] = visited[next]; que.push(mv_next); } continue ; } que.push(next); } } } } void solution() { bfs(); } 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)); } } void preset() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } int main() { preset(); input(); solution(); output(); }
C++
복사