백준 13913번: 숨바꼭질 4 - BFS, DFS 활용

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

13913번: 숨바꼭질 4

1.문제설명

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.

순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이가 동생을 찾는 최소 시간과 경로(여러가지 중 하나)를 구해야한다.

 

2.접근방법[알고리즘]

수빈이가 동생을 찾는 최단 경로를 구하기 위해 BFS를 활용해주면 된다.

수빈이가 방문하는 점에 대해서 ch배열에 저장해주고, ch배열에는 이전 노드의 값을 저장해준다.

이전 노드의 값을 저장해주면 후에 재귀함수를 돌면서 경로를 쉽게 구해줄 수 있다.

void DFS(int x) {
	if (ch[x] == -1) {
		cout << x << ' ';
	}
	else {
		DFS(ch[x]);
		cout << x << ' ';
	}
}

ch[17] == 16

ch[16] == 8

ch[8] == 4

ch[4] == 5

 

숨바꼭질 메모리 초과 , 시간초과 이유

단 위 문제에서 노드를 0번부터 쓰기 때문에 ch[1] = 0 이된다. 

그렇기 떄문에 방문하지 않은 점인지 확인할 때

ch[x]==0 을 확인하는 게 아니라

0이 아닌 사용하지 않는 다른 값으로 초기화해주고 그 값을 통해 확인해주어야한다.

아래 코드에서는 ch[x] = -10 으로 초기화 해놓고 ch[x] == -10 이라면 방문하지 않은 점으로 확인해주었다.

 

만약 0으로 확인해주면

ch[1] == 0 인데, 2번 노드에서 BFS를 할 때

ch[1] == 2로 다시 변경된다. 이러면 ch[2]==1 이어서

위 DFS코드에서 1과 2를 무한 번 돈다.

무한 반복해서 시간초과나 메모리초과가 발생하게 된다.

 

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, k;
// ch에 이전 방문지 저장
int ch[100001];

//방문 노드 출력 함수
void DFS(int x) {
	if (ch[x] == -1) {
		cout << x << ' ';
	}
	else {
		DFS(ch[x]);
		cout << x << ' ';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
    
	for (int i = 0; i < 100001; i++) {
		// 0으로부터 움직이는 경우도 있기 때문에 초기화
        // ch[i] == -10이면 아직 방문 안한 곳
		ch[i] = -10;
	}


	cin >> n >> k;
	
	//위치, 시간 저장
	queue<pair<int, int> > Q;

	Q.push({ n,0 });
	ch[n] = -1;

	while (!Q.empty()) {
		int x = Q.front().first;
		int t = Q.front().second;
		Q.pop();
        
		if (x == k) {
			cout << t <<'\n';
			DFS(k);
			return 0;
		}

		if (x - 1 >= 0 && ch[x-1] == -10) {
			ch[x - 1] = x;
			Q.push({ x - 1, t + 1 });
		}
		if (x + 1 <= 100000 && ch[x + 1] == -10) {
			ch[x + 1] = x;
			Q.push({ x + 1,t + 1 });
		}

		if (2 * x <= 100000 && ch[2 * x] == -10) {
			ch[2 * x] = x;
			Q.push({ 2 * x,t + 1 });
		}

	}

}

백준 13913

문제풀이후기

check배열에 이전 방문한 노드를 저장해 줄 때 노드를 0번도 사용 한다면 

방문한 노드인지 비교할 때 초기화에 대해서 한 번 더 생각해주어야 한다.