백준 16928번 뱀과 사다리 게임 C++ BFS

리뷰

쉬워보이나 판별조건을 잘 설정해 주어야 하는 문제

 

문제 풀이

방문배열을 일반 방문배열, 사다리 방문배열, 뱀 방문배열 총 세개 만들어 준다. 

사다리와 뱀의 위치를 index로 이동할 위치를 value로 입력 받아준다.

1부터 bfs를 시작해 주고 현재 위치부터 1 ~ 6까지 for문을 돌려준다.

도착 위치가 사다리라면 사다리를 타고 해당 위치로 이동 후 방문 배열에 추가해 준다.

도착 위치가 뱀이라면 뱀을 타고 해당 위치로 이동 후 방문배열에 추가해 준다.

둘 다 해당하지 않다면 주사위 위치로 이동 후 방문 배열에 추가해 준다.

현재 위치가 100이라면 소요 시간을 출력해 준 후 리턴해 준다.

 

참고 사항

사다리나 뱀이 이미 방문한 위치라면 continue를 해줘야 한다. 해당 부분땜에 시간이 좀 걸렸다.

 

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int v[101] = { 0, };
int ladder[101] = { 0, };
int snake[101] = { 0, };

struct pos {
	int x, time;
};

void bfs(int row) {
	queue<pos> q;
	q.push({ row, 0 });
	v[row] = 1;

	while (!q.empty()) {
		pos now = q.front();
		q.pop();
		int x = now.x, time = now.time;
		if (x == 100) {
			cout << time;
			return;
		}
		for (int i = 1; i < 7; i++) {
			int nrow = x + i;
			if (nrow < 101 && !v[nrow]) {
				v[nrow] = 1;
				if (ladder[nrow]) {
					if (v[ladder[nrow]]) continue;
					v[ladder[nrow]] = 1;
					q.push({ ladder[nrow], time + 1 });
				}
				else if (snake[nrow]){
					if (v[snake[nrow]]) continue;
					v[snake[nrow]] = 1;
					q.push({ snake[nrow], time + 1 });
				}
				else {
					q.push({ nrow, time + 1 });
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		ladder[a] = b;
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		snake[a] = b;
	}
	bfs(1);
}