[백준 13913] 숨바꼭질 4

 

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

13913번: 숨바꼭질 4

#include <cstdio>
#include <queue>
int N, K;
struct _st
{
	int X;
	int t;
};
std::queue<_st> Q;

int chk[100000 + 10];
int path[100000 + 10];


void init(void)
{
	for (int i = 0; i <= 100000; i++) {
		chk[i] = 0x7fffffff;
		path[i] = -1;	// 엣지케이스때문에 -1로 초기화
	}
}

int BFS(void)
{
	Q.push({ N, 0 });	// 현재위치, 0초 걸림
	chk[N] = 0;

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

		int pos[3] = { -1, 1, data.X };

		for (int i = 0; i < 3; i++) {
			int nx = data.X + pos[i];
			int nt = chk[data.X] + 1;

			if (nx < 0 || nx > 100000) continue;
			if (chk[nx] <= nt) continue;
			chk[nx] = nt;
			path[nx] = data.X;	// 경로 역추적 위해
			Q.push({ nx, nt });
		}
	}
	return chk[K];
}


void print_route(int n)
{
	if (n == -1) return;
	print_route(path[n]);
	printf("%d ", n);
}


int main()
{
	scanf("%d %d", &N, &K);
	init();
	int ans = BFS();
	printf("%d\n", ans);
	print_route(K);
	return 0;
}

숨바꼭질 조졌다 ㅋ 깔깔! 나새끼 칭찬해 

 

이 문제는 "수빈이가 동생을 찾을 수 있는 가장 빠른 시간"을 구하는 BFS 함수 구현 쪽은 실버 문제와 다른게 없다. 

다만 추가적으로 "어떻게 이동해야 하는지"에 대한 정보를 출력해야 한다.

 

// BFS( ) 함수

경로를 역추적 하기 위해 path 배열을 선언했다. 굳이 이 배열을 -1로 초기화 한 이유는 후에 밝히겠다. 

해당 배열은 "path[현재 위치] = 이전 위치" 와 같이 저장했다. 현재위치가 주어졌을 때, 그 값이 이전경로가 되는 방식이다. 

예제 입출력을 참고하면,

//input
5 17

//output
4
5 10 9 18 17

이때 현재위치가 17이라면, 이전위치인 18이 인덱스 17의 값으로 담기는 것이다. (path[17] = 18)

 

 

// print_route( ) 함수

위와 같이 배열을 구성한 이유는, 동생의 위치 K에서 수빈이의 처음 위치인 N까지 역으로 추적하기 위함이다. 

초기 파라미터를 동생위치인 K를 주고, print_route(path[K]) 와 같이 재귀적으로 함수를 호출한다. 즉, 예제 입출력에서 17을 초기 파라미터로 주고, 17 - > 18 -> 9 -> 10 - > 5 이렇게 역추적 하는 것이다. 

 

그런데 만약 path배열을 0으로 초기화 하고, 재귀함수를 (n == 0)일때 리턴하면 다음과 같은 테스트케이스에서 문제가 생긴다. 

//input
1 0

//output - Wrong
1

//output - AC
1
1 0

재귀함수 print_route의 초기 파라미터인 K가 0이기 때문에 경로를 출력하지 못하고 들어오자마자 리턴되는 것이다. 

따라서 이러한 엣지 케이스를 해결하기 위해 path 배열을 -1로 초기화하였다.

 

 

흠.. 아직 이렇게 코너케이스들 다루는게 서투른 것 같다... 뭐 어쩌겠어요.. 더 풀어야지..