[백준 16928] 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

#include <cstdio>
#include <queue>
int N, M;
int visited[100 + 2];
int Move[100 + 2];


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N + M; i++) {
		int s = 0, e = 0;
		scanf("%d %d", &s, &e);
		Move[s] = e;
	}
}

void init()
{
	for (int i = 0; i <= 100; i++) {
		visited[i] = 0x7fffffff;
	}
}



int BFS()
{
	std::queue<int> Q;
	Q.push(1);
	visited[1] = 0;

	while (!Q.empty()) {
		int data = Q.front();
		Q.pop();

		if (data == 100) return visited[100];

		for (int d = 1; d <= 6; d++) {
			int ndata = data + d;

			if (ndata > 100) continue;
			if (Move[ndata] != 0) ndata = Move[ndata];
			if (visited[ndata] <= visited[data] + 1) continue;
			Q.push(ndata);
			visited[ndata] = visited[data] + 1;
			//printf("%d %d\n", d, ndata);
		}
	}
	return -1;
}



int main()
{
	input();
	init();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

 

각 번호에 도착하는 cost가 다르기 때문에 메모이제이션 해주어야 하는 문제였다.

이를 위해 visited배열을 초기에 아주 큰 값(0x7fffffff) 으로 초기화해주었다. 

 

 

++ 예전 풀이들 (조잡 주의)

#include <cstdio>
#include <queue>
int N, M;
struct _st
{
	int n;
	int c;
};

std::queue<_st> Q;
bool visited[100 + 2];
int move[30 + 2][30 + 2];
int flag = 0;


void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < (N + M); i++) {
		scanf("%d %d", &move[i][0], &move[i][1]);	// 사다리와 뱀
	}
}

int BFS(void)
{
	Q.push({ 1, 0 });
	visited[1] = true;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();
		if (data.n == 100) return data.c;

		for (int i = 1; i <= 6; i++) {
			int nn = data.n + i;
			flag = 0;
			if (nn > 100 || visited[nn]) continue;
			
			for (int j = 0; j < (N + M); j++) {
				if (nn == move[j][0]) {
					int mn = move[j][1];
					flag = 1;
					visited[mn] = true;
					Q.push({ mn, data.c + 1 });
				}
			}
			if (flag == 0) {
				visited[nn] = true;	// 뱀과 사다리 출발지점 visited 체크 해주면 안됨....
				Q.push({ nn, data.c + 1 });
			}
		}
	}
}


int main()
{
	input();
	int ans = BFS();
	printf("%d", ans);
	return 0;
}

음.. 내코드.. 맘에들지는 않지만 일단 기록해본다. 다시 풀어보고 더 좋은코드가 나온다면 수정하겠다. 

일단 코드를 처음 설계할 때 내가 간과한 사실 몇 가지는 다음과 같다. 

1. 어차피 cost가 동일하기 때문에 chk 배열을 두고 매번마다 최단거리를 비교해줄 필요가 없다.

2. 뱀이나 사다리를 타면 cost가 증가하지 않는다. 

3. 주사위로 이동한 곳에 뱀이나 사다리가 있다면, 출발점은 방문처리 해주지 않고 "도착점만 방문처리" 한다. (*중요)

 

그래서 주사위 일단 다 돌리고 -> 뱀이나 사다리를 타도록 코드를 구현하거나, 주사위 돌리면서 뱀이나 사다리를 탈 수 있는 위치인지 확인하더라도, 출발점을 방문처리해주면 22%에서 wrong answer가 뜬다 ㅎ(내가 해봄 ^^ 많~이 해봄 ^^)

 

그래서 어떻게 처리할까 하다가.. 나는 flag를 달아서 뱀이나 사다리를 타고 이동한 경우 flag 를 1로 갱신해주고, 출발점을 방문처리 및 큐에 삽입하지 않도록 구현했다. 

 

아... 이 글을 작성하면서 내가 간과한 부분을 하나 더 발견했다... ㅋㅋㅋㅋㅋ

4. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 

이 조건을 통해 for 루프 한개를 줄일 수 있다. 뱀과 사다리의 경우를 2차원 배열에 넣어서 N + M 번 탐색하도록 구현했는데, 어차피 특정 칸에 뱀이나 사다리가 1개 이상 있는 경우는 없으므로, 일차원 배열에 move[출발점] = 도착점 이렇게 담아주고 바로바로 확인해도 될 것 같다..... 

 

 

음..... 나레기.. 

#include <cstdio>
#include <queue>
int N, M;
int moves[100 + 2];
bool visited[100 + 2];

struct _st
{
	int n;
	int c;
};
std::queue<_st> Q;

void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < (N + M); i++) {
		int u = 0; int v = 0;
		scanf("%d %d", &u, &v);
		moves[u] = v;
	}
}


int BFS(void)
{
	Q.push({ 1, 0 });
	visited[1] = true;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.n == 100) return data.c;

		for (int i = 1; i <= 6; i++) {
			int nn = data.n + i;
			if (nn > 100 || visited[nn]) continue;	// 새로운 위치가 100을 넘어가거나 방문했으면 스루

			if (moves[nn] != 0) nn = moves[nn];		// 해당 칸에 뱀이나 사다리가 있으면 무조건 탐
			visited[nn] = true;	
			Q.push({ nn, data.c + 1 });
		}
	}
}


int main()
{
	input();
	int ans = BFS();
	printf("%d", ans);
	return 0;
}

확실히 뱀이나 사다리로 이동하는 경우를 일차원 배열로 구현하고, 루프 하나 빼니까 훨씬 깔끔해 보인다. 굿굿

상기 코드에서는 갱신한 nn 위치가 100을 넘어가거나 방문한 경우가 있다면 스루한다. 

그리고 해당 칸에 뱀이나 사다리가 존재한다면(moves[nn] != 0) 출발점인 nn을 끝점 moves[nn]으로 갱신해준다. 

그리고 nn 위치에 대한 방문처리와 큐 삽입을 가장 나중에 한 번만 진행해주었다.