[bfs][최단거리] 뱀과 사다리 게임 16928

문제 해설 및 주의사항

1. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.

 

2.  도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

 

3. 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다.

 

---

 

풀이

1. 비슷한 문제 ( bfs 를 활용한 최단거리 )

 

2. 뱀과 사다리에 연연하지 않기

- 한 좌표에서 다른 좌표로 간다. 라는 점이 공통이므로, x -> y 로 간다는 next_blank 배열을 이용했다.

 

3. bfs 와 최단거리

- 위의 비슷한 문제에서도 풀었듯이, 같은 bfs 처리를 해주면 된다. 이전 좌표에서의 거리 + 1 이 현재 까지의 거리라는 점을 이용하자.

---

풀이코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

// 거리를 의미하는 배열
int dist[101];
// 사다리나 뱀의 정보 혹은 일반 칸의 정보
// next_blank[i] = j 라면, i 번째 칸의 다음 칸은 j 라는 뜻.
int next_blank[101];

int main(){
	int n, m;
	cin >> n >> m;
	
	for(int i = 1; i <= 100; i++){
		// 일반 칸이라면 그냥 자기 자신
		next_blank[i] = i;
		dist[i] = -1;
	}
	
	// 사다리
	while(n--){
		int x, y;
		cin >> x >> y;
		next_blank[x] = y;
	}
	
	// 뱀
	while(m--){
		int x, y;
		cin >> x >> y;
		next_blank[x] = y;
	}
	
	// 시작 처리
		// 첫 시작의 거리는 0
		dist[1] = 0;
		queue<int> q;
		q.push(1);
	
	// bfs 시작
	while(!q.empty()){
		// x : 현재 칸
		int x = q.front(); q.pop();
		
		for(int i = 1; i <= 6; i++){
			// i : 나온 주사위 값
			// y : 다음 칸 
			int y = x + i;
			
			// 범위 체크
			if(y > 100) continue;
			
			// 사다리 / 뱀 / 일반 칸인지 next_blank 배열을 통해 구분. 실제 다음 칸을 구함.
			y = next_blank[y];
			
			// 아직 거리 계산을 안한 칸이라면
			if(dist[y] == -1){
				// 거리는 이전 칸의 +1
				dist[y] = dist[x] + 1;
				q.push(y);
			}
		}
	}
	printf("%d\n", dist[100]);
	return 0;
}

 

---

퇴고