문제
주사위를 굴리면서 맵을 이동하는 보드게임을 떠올리면 된다. 도착한 칸이 사다리 혹은 뱀이면 반드시 그것을 따라 이동한다는 조건이 주어져 있다. 사다리면 앞으로 가고 뱀이면 뒤로 이동한다곤 하지만 최단 이동 횟수를 찾는다는 점에서 크게 중요한 건 아니다.
게임판이 10*10이라고 설명했음에도 입력되는 뱀/사다리 위치의 좌표는 x번 칸, 즉 1차원으로 주어졌다. 대표적인 그래프 문제인 숨바꼭질 문제가 유사하다는 걸 확인할 수 있으며, 32번 칸에 도착하면 반드시 62번 칸으로 이동한다는 점, 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있다는 점에서 key-value의 매핑 관계, 즉 map 자료구조를 도입하는 것을 떠올릴 수 있다.
BFS로 이를 해결하려면, 방문하는 노드마다 이 노드를 방문하는 횟수를 저장하고 있어야 한다는 생각에 visited 배열을 채택할 수 있다. visited를 큰 수로 초기화한 다음, BFS를 통해 각 칸들을 순회하며 큐가 비었을 때 visited[100]의 최솟값을 출력하면 된다.
현실세계에서 주사위는 무작위지만, 여기서는 가능한 모든 시나리오 중 최단 거리롤 100까지 도착하는 것을 찾아야 하기에, 주사위를 던지는 로직은 1~6까지 모든 경우를 큐에 담아두어야 한다. 그러면서 그 좌표에 뱀과 사다리가 있는지, 즉 이 위치가 map 내부의 key 명단에 존재하는지 파악해야 한다. (map.count를 사용할 수 있다.)
소스 코드
#include <iostream>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
int n, m;
int visited[101]; // 방문 여부 확인
map<int, int> w; // 사다리와 뱀
queue<int> q; // BFS
void BFS(){
visited[1] = 0; // 최초 좌표의 방문 횟수는 0이다.
for(int i=2; i<=7; i++){
if(w.count(i) > 0){ // 이 위치에 사다리 혹은 뱀이 존재하는 경우
q.push(w[i]);
visited[w[i]] = 1;
} else {
q.push(i);
visited[i] = 1;
}
} // 최초 주사위 던지기
while(!q.empty()){
int x = q.front();
q.pop();
if(x >= 100) continue; // 100 이상인 경우 배제
for(int i=1; i<=6; i++){
int nx = 0;
if(w.count(x+i) > 0){ // 사다리 혹은 뱀이 존재하는 경우
nx = w[x+i];
} else {
nx = x+i;
} // 다음 좌표를 결정한다.
if(nx > 100) break; // 100 초과면 배제
if(visited[nx] > visited[x] + 1){ // visited 최솟값으로 갱신
visited[nx] = visited[x] + 1;
q.push(nx);
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i=0; i<n+m; i++){
int a, b;
cin >> a >> b;
w[a] = b;
} // 사다리 및 뱀에 대한 정보 입력
memset(visited, 10000, sizeof(visited));
BFS();
cout << visited[100] << '\n';
return 0;
}교훈
- map 자료구조를 적재적소에 활용할 수 있도록 관련 메서드(count 등)를 알아두어야 한다.
- visited 배열의 자료형을 bool(단순 방문여부)이나 int(최단 방문횟수 등 추가적인 역할 부여)중 어느 것으로 설정할지 문제를 잘 읽고 정확한 판단이 필요하다.
Discover Tomorrow