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++
복사
