백준 13913 (숨바꼭질 4)

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

13913번: 숨바꼭질 4

해당 문제는 수빈이가 동생을 찾는데 까지 걸리는 시간과 해당 시간동안 이동한 위치를 출력하는 문제이다. 

BFS를 사용하여 완전탐색을 시행하며 최단 거리를 출력하면 된다. 이때 주의할 점은 다음과 같다.

1. 수빈이가 이동한 위치를 기록할 Vector 생성 후 해당 벡터에 계속 push 하는 과정을 통해 위치를 저장하고 출력하면 된다. 하지만 수빈이의 위치가 100,000 이며 동생의 위치가 0이라면 어떻게 될까 분명히 메모리 복사, 메모리 사용량 초과와 같은 애러가 발생할 것이다.

위의 조건을 잘 읽어보자 이전으로 이동할 때에는 오직 -1 칸 밖에 움직이지 못한다 따라서 수빈이의 위치 - 동생의 위치를 이용하면 최소 이동 횟수를 구할 수 있으며 수빈이의 위치부터 동생의 위치까지 계속 -- 연산을 통해 출력해주면 된다.

#include <iostream>
#include <string>
#include <queue>
using namespace std;
int start, target, k;
int check[3] = { +1, -1, 2 };
int map[100001];
int visit[100001];
int cpVisit[100001];

struct Node{
	int idx, cnt;
	vector<int> vect;
};

void bfs(int start){
	queue<Node> qu;
	qu.push({ start, 0 });
	qu.front().vect.push_back(start);
	visit[start] = 1;
	
	while (!qu.empty()){
		Node now = qu.front();

		for (int i = 0; i < 3; ++i){
			int dx = now.idx + check[i];
			if (i == 2) dx = (now.idx * 2);
			if (dx < 0 || dx > 100000 || visit[dx] == 1) continue;
			if (dx == target) {
				int n = now.vect.size();
				printf("%d\n", now.cnt + 1);
				for (int i = 0; i < n; ++i){
					printf("%d\n", now.vect[i]);
				}
				printf("%d\n", dx);
				return;
			}
			visit[dx] = 1;
			vector<int> tmp = now.vect;
			tmp.push_back(dx);
			qu.push({ dx, now.cnt + 1, tmp });
			
		}
		qu.pop();
	}
	return ;
}

int main(){
	// freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> start >> target;
    
    // 동생이 수빈이 보다 뒤에 있을경우
	if (target < start){
		printf("%d\n", start - target);
		for (int i = start; i >= target; --i){
			printf("%d\n", i);
		}
	}
	else if (start == target){
		printf("0\n");
		printf("%d\n", start);
	}
	else{
		bfs(start);
	}
}