백준 12851 C언어

백준 12851숨바꼭질2 문제이다.

숨바꼭질1 문제에선 이미 BFS방식으로 Queue에 숫자를 넣어 층을 구별하면서 Pop하여 층을 더해줄 수 있었다.

Visit[]을 만들어 이미 조사된 숫자는 조사하지 않고 목표 숫자를 만나면 함수 동작을 return하여 조사를 마친다.

 

하지만, 이번 숨바꼭질2에선 같은 최소 경로의 층에서 그 숫자의 개수를 추가로 세야한다.

 

1) 처음에는 중복된 숫자도 조사하는 방식으로 찾아보려 했는데 그렇게 되면 3^(층 수)이하만큼 커지게 되어 배열의 숫자가 어마어마하게 커진다.    ....(X)

 

2) 중복된 숫자를 조사하는 대신 중복된 숫자를 Visit[]에 넣는 방식을 택했다. 하지만, 이렇게 되면 최소 경로의 수가 아닌 조사한대로 나오게 되고, 하면서 생각해보니까 중복된 숫자를 Visit[]에 넣으려면 그 숫자도 조사해야해서 1)의 방식이랑 차이가 없었다.    ...(X)

 

3) 조사된 숫자랑 짝이되는 층 수를 저장한다.  만약에 2라는 숫자가 1층에서 최소 경로로 나온다면 2와 1층은 서로 짝이된다. 2는 1층에서 안나오면 최소경로가 아니게 된다. 2에 파생된 숫자 2*2 = 4는 2다음에도 나오지만 3+1=4가 나올 수도 있다. 이 4라는 숫자는 어디서 최소 층수랑 짝이 되는지는 모른다. 하지만, 2에서 파생된 4는 2가 최소경로가 아니라면, 2에서 파생된 4는 최소는 아닐 것이다. ( = 4또한 부모인 2가 최소가 아니므로) 그래서 우리는 2가 나왔을 때  2는 오직 그 층 수에서만 조사하고 2가 그 층(1층)이 아니라면 그 이하의 층(3층이상)부터는 조사하지 않아도 된다. 그러면 그 이상의 층에서 2가 나온다면 우린 그 2가 최소 경로는 아님을 알 수 있고 그 2에서 파생된 숫자들도 최소 경로가 아님을 알 수 있다.

따라서, 각 층 에서 나온 숫자들의 개수와 대응되는 층 수를 파악하고 다음 층에서는 조사하지 않는다.

층 수를 Queue에다가 미리 넣어놓고 Pop할 때, Visit[n]에 방문 숫자를 적어 출력하면 된다.    ....(O)

 

아래는 예시의 그림이다.

---

 

#include <stdio.h>
int Queue[25000000] = { 0, };  // Queue에 얼마나 들어갈지 몰라서 최대 숫자를 할당.
int Visit[100001] = { 0, }; // 0~100,000의 수.
int depth = 0, check = 0;
int start, end;
int size;
void BFS(int num) {
	int Pop;
	int front=0, rear=1;	
	Queue[0] = num;
	Visit[num] = 1;
	while (front < rear) {
		size = rear - front;
		for (int i = 0; i < size; i++) {
			Pop = Queue[front]; 
			Visit[Pop]++; // Push하면서 방문처리를 하면 Pop할 때 중복허용이 안됨.
			if (Pop == end)
            			check = 1;
			if (!Visit[Pop + 1] && Pop + 1 <= 100000 && Pop + 1 >= 0) 		
				Queue[rear++] = Pop + 1;	
			if (!Visit[Pop - 1] &&  Pop - 1 <= 100000 && Pop - 1 >= 0)		
				Queue[rear++] = Pop - 1;
			if (!Visit[Pop * 2] && Pop * 2 <= 100000 && Pop * 2 >= 0)				
				Queue[rear++] = Pop * 2;		
			front++;
		}
		if (check == 1) {
			printf("%d\n%d", depth, Visit[end]);
			return;
		}
		depth++;
	}
}

int main() {
	scanf_s("%d %d", &start, &end);
	if (start == end) { // 같은 숫자일 경우, 방법은 하나.
		printf("%d\n%d", depth,1);
		return 0;
	}
	BFS(start);
	return 0;
}