백준) 16928 - 뱀과 사다리 게임

이번에는 BFS에 대해서 공부하기 위해 뱀과 사다리 게임을 풀어봤다. (Solved.ac기준 실버 3)

처음에는 어떤 방식으로 풀어야 할지 역시 막막했음 ㅠ

 

그런데 숨바꼭질(1697)을 풀어보니 대충 어떤 느낌인지 감 잡을 수 있었다.

 

간단 요약을 하자면 큐에 넣고 큐 사이즈만큼 for문 돌리고!!!! 큐에서 빼고!!!! 계속 큐에 넣고!!!!!

 

<문제>

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

16928번: 뱀과 사다리 게임

 

<코드>

#include <iostream>
#include <queue>

using namespace std;

int N, M, count;
bool check[101] = {0, };
vector<pair<int, int> > lns;	

void bfs() {
	count = 0;
	queue<int> q;
	q.push(1);
	while(!q.empty()) {
		int size = q.size();
		for(int i = 0; i < size; i++) {
			int x = q.front();
			q.pop();
			if(x == 100) {
				cout << count << endl;
				return;
			}
			for(int j = 0; j < N+M; j++) {
				if(x == lns[j].first)
					x = lns[j].second;
			}
			for(int j = 1; j <= 6; j++) {
				if(check[x+j] == false && x+j < 101){
					q.push(x+j);
					check[x+j] = true; 
				}
			}
		}
		count++;
		
	}
	
}

int main(void) {
	int a, b;
	cin >> N >> M;
	for(int i = 0; i < N+M; i++) {
		cin >> a >> b;
		lns.push_back(make_pair(a, b));
	}
	bfs();
	
	return 0;
}

설명 들갑니다잉

check : 방문 여부 확인

vector<pair<int, int> > lns : Ladder & Snake - first에서 second로 이동

count를 통해 최솟값 구하기

 

bfs함수

먼저 큐에 1을 넣는다. (1부터 시작해서 주사위를 던지니까!!!!)

그리곤 while문을 돌려 Queue가 비어있을 때까지 (혹은 그냥 무한으로) 돌린다!

큐에 있는 모든 값들에 가능한 경우의 수들을 큐에 다시 넣어서 최솟값을 구한다.

이때, 주사위를 던졌는데 100이 넘어가면 안 된다.

또한, 사다리나 뱀 지역에 닿았을 때는 이동시켜준다. - 이 부분에서 주사위를 던졌는데 first에 도착을 했으면 first를 큐에 넣어주고 다시 while문을 통해 돌아왔을 때, second로 이동시켜주고 계속 진행한다.

무한 반복!!!!! x 가 100이 나올 때까지!!!!!!

 

BFS 어떻게 쓰는지 솔직히 헷갈렸는데 하나하나 써가면서 하니 대충 느낌이 왔다.

기분 죠으다 ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ

 

위는 while(1) 아래는 while(q.empty())