Memo
게임판을 굳이 이차원 배열로 표현하지 않아도 됩니다.
게임의 목표는 1번 칸에서 시작해서 100번 칸으로 이동하는 것이고, 입력을 보면 "x번 칸에 도착하면, y번 칸으로 이동" 이기 때문에 굳이 이차원 배열로 표현하지 않았습니다.
BFS
1번 칸 부터 시작하여, 주사위로 굴려 이동할 수 있는 모든 경우의 수를 조사합니다. queue에 (이동한 칸, 주사위를 굴린 횟수)를 넣고 뺌으로써 가까운 거리부터 조사해 나갑니다.
Visited check
한 번 방문한 곳을 다시 방문한 경우에는 continue를 통해 더 이상 큐에 넣지 않습니다. 그 이유는, 이전에 방문한 경우에서 주사위를 굴려 이동가능한 경우의 수는 현재 다시 방문한 경우의 경우의 수와 완전히 동일하기 때문입니다. 이전에 방문한 경우는 현재 방문했을 때 까지의 주사위를 굴린 횟수보다 작거나 같습니다. (가까운 거리부터 조사하는 BFS의 특성상)
Code
제출 날짜
@4/3/2021
메모리
2016 KB
시간
0 ms
#include <iostream>
#include <queue>
int N, M;
int ladder_snake[101];
bool visited[101];
int dice[6] = {1,2,3,4,5,6};
int ans;
std::queue<std::pair<int, int> > q; // 몇 번째 칸인지, 주사위 굴린 횟수
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int x, y;
input_faster();
std::cin >> N >> M;
for (int i = 0 ; i < N ; i++)
{
std::cin >> x >> y;
ladder_snake[x] = y;
}
for (int i = 0 ; i < M ; i++)
{
std::cin >> x >> y;
ladder_snake[x] = y;
}
}
void bfs()
{
int qx, qy, nx, ny;
q.push({1, 0});
visited[1] = 1;
while (!q.empty())
{
qy = q.front().first; //몇 번째 칸인지
qx = q.front().second; //주사위를 지금까지 얼마나 굴렸는지
q.pop();
for (int i = 0 ; i < 6 ; i++)
{
ny = qy + dice[i];
nx = qx + 1;
if (ny <= 0 || ny > 100 || visited[ny])
continue;
if (ny == 100)
{
ans = nx;
return ;
}
visited[ny] = 1;
if (ladder_snake[ny]) // 사다리, 뱀 칸이면
{
if (visited[ladder_snake[ny]])
continue;
visited[ladder_snake[ny]] = 1;
q.push({ladder_snake[ny], nx});
}
else
q.push({ny, nx});
}
}
}
void solve()
{
bfs();
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
