숨바꼭질2

전형적인 BFS 문제랑은 조금 다른문제다.

전에 풀었던, 숨바꼭질4는 트랙킹, 그리고 DSLR은 트랙킹이아닌 하면서 경로 같이쓰기

하지만 이문제는 경로에 관한 정보가아닌 경로의 가짓수를 물어본다.

 

경로의 가짓수는 잘알고있듯 , DP로 푸는게 빠른편인데,

BFS를 해서 최소 가짓수를 구하고, 가짓수를 구하는 동안에 DP를 사용해서 가짓수도구할수있다.

사실 2차원배열문제였다면 많이 어려웠을거 같다는 생각이 들지만, 1차원이라 DP도 쓰기편했다.

 

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdlib>


using namespace std;

bool d[1000000];
int go[1000000];
int cnt[1000000];
int ans = 0;

int su, little;

void bfs() {
	queue<int> q;
	q.push(su);
	d[su] = true;
	cnt[su] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (x + 1 <= 100000) {
			if ((d[x + 1] == false)) {
				d[x + 1] = true;
				go[x + 1] = go[x] + 1;
				cnt[x + 1] = cnt[x];
				q.push(x + 1);
			}
			else if (go[x + 1] == go[x] + 1) {
				cnt[x + 1] += cnt[x];
			}
		}
		
		if (x - 1 >= 0) {
			if (d[x - 1] == false) {
				d[x - 1] = true;
				go[x - 1] = go[x] + 1;
				cnt[x - 1] = cnt[x];
				q.push(x - 1);
				
			}
			else if (go[x - 1] == go[x] + 1) {
				cnt[x - 1] += cnt[x];
			}
			
		}
		if (x * 2 <= 100000 ) {
			if ((d[x * 2] == false)) {
				d[x * 2] = true;
				go[x * 2] = go[x] + 1;
				cnt[x * 2] = cnt[x];
				q.push(x * 2);
			}
			else if (go[x*2] == go[x] + 1) {
				cnt[x*2] += cnt[x];
			}
		}
	}
}


int main() {
	scanf("%d %d", &su, &little);
	int counting = 0;
	bfs();
	/*for (int i = 0; i < 20; i++) {
		printf("cnt[%d] = %d\n", i, cnt[i]);
	}*/
	printf("%d\n%d\n", go[little], cnt[little]);
	return 0;
}

DP는 배열 cnt를 통해서 했고, 만약에 중복된 가짓수가 생길때( 이미 가려는곳을 방문했을때) 해당 방문지의 go배열값을 비교해서, cnt값 즉 가짓수를 늘려가는방식으로 사용했다.