백준 16928번 뱀과 사다리 게임

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

 

 

 

 

 

<접근방법>

bfs 문제입니다.

해당 지점이 뱀인지 사다리인지는 중요하지 않습니다.

다만 그 지점이 다른 좌표로 이동한다는 사실입니다.

그래서 2차원 배열을 만들고 그 지점이 이동할 좌표를 저장해주었습니다.

뱀 혹은 사다리가 아닌 경우에는 그 지점의 좌표를 저장했습니다.

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

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

int n, m, map[11][11], res;
bool visit[101];

queue<int> q;

void bfs() {
	q.push(0);
	visit[0] = true;

	while (!q.empty()) {
		int sz = q.size();
		for (int z = 0; z < sz; z++) {
			int now = q.front();
			q.pop();

			if (now == 99) {
				return;
			}

			for (int i = 1; i <= 6; i++) {
				int next = now + i;
				int ny = next / 10;
				int nx = next % 10;

				if (next > 99 || visit[next]) continue;

				visit[next] = true;

				int np = map[ny][nx];

				q.push(np);
			}
		}
		res++;
	}
}

int main() {
	int num = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			map[i][j] = num++;
		}
	}

	cin >> n >> m;

	while (n--) {
		int a, b, ay, ax, by, bx;
		cin >> a >> b;
		a--; b--;
		
		ay = a / 10;
		ax = a % 10;

		map[ay][ax] = b;
	}
	while (m--) {
		int a, b, ay, ax, by, bx;
		cin >> a >> b;
		a--; b--;

		ay = a / 10;
		ax = a % 10;

		map[ay][ax] = b;
	}

	bfs();

	cout << res << '\n';

	return 0;
}