백준 1525번 퍼즐 BFS 최단,최소 문제. DFS는 힘든이유..

 

퍼즐 문제는 메모리가 매우 적게 제한된 문제이다.

 

보통 최단문제의 경우 BFS로 접근하는게 일반적이지만,

BFS의 경우 매 단계마다 가능한 경우의 수를 모두 queue에 저장해야되므로

상태를 저장해야되는 맵정보를 처음에 vector로한 결과 메모리가 초과되는 문제가 있었다.

 

그래서, 한번에 최대깊이까지만,,, 최대 메모리를 사용하고, 그 이상으로 메모리를 사용하지 않는

DFS로 접근을 시도했다. DFS의 경우, map정보를 전역 혹은, 매개변수를 포인터로 넘겨주고,

return시에 다시 맵을 원상복귀 시켜주기만 한다면, DFS의 깊이와 상관없이

map 한개의 메모리양만 사용하게 설계할 수 있다.

하지만 이 문제는 기본적으로 DFS로 접근이 힘들다.

 

1. DFS특성상 최단문제에 적합하지 않다.

   그 이유로는, 현재 목표 상태에 도달한 것이 최단으로 도달했다는 보장이 없다.

   그렇기 때문에 brute하게 한번 도달했던 상태 또한 다음에 또 수행될 가능성을 남겨주어야한다.

   그래서 같은 상태에 도달했더라도 더 빠르게 도달했다면, 갱신과 백트래킹 방식으로 설계해야하므로

   알고리즘이 매우 느려지거나, 혹은 언젠가 return된다는 보장이 없다면

   dfs의 상태가 순환에 빠지게 될 수도 있다. DFS는 언젠간 return될 수 있는 기저가 항상 필요하다.

 

 

2. 마지막 방법으로, 수학적인 접근법으로 DFS에서 최적으로 백트랙킹할 수 있는 구간을 잡는 것이 있다.

   즉 dfs가 현재 상태가 더 이상 가망이 없다고 판단하면, 더 실행하지 않는 방식이다.

   

   이 문제의 경우 더 이상 진행될수 없다 판단되는 상태를 여러개 코딩해서 넣어봤지만...그럼에도

   dfs가 상태가 순환에 빠지는 경우가 생기는것 같다.

 

 

결론 BFS로 가자..

BFS가 최단문제에 적합한 이유는, 현재 도달한 상태가 최단으로 도달했다는 것이 보장되어 있기 때문에

(단계를 넘어가는 비용이 모두 같다는 전제)

이미 가봤던 상태를 또 시도할 필요가 없으므로 도달했던 상태를 체크한다면,

순환에 빠지지 않고, 최적의 길을 찾을 수 있다.

 

queue에 넣는 맵정보를 최대한 작은 자료형으로 줄였더니 성공하였다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#include<queue>
using namespace std;


// bfs로 풀기엔 주어진 메모리도 적고 메모리가 부족할거 같아서
// dfs로 풀어보려했더니,,,,dfs의 경우 이미 방문했던 경우의 수가 최단이라는 보장이 없기에
// visit을 찍으면 안된다. 그렇다면 backtracking할 지점을 설정해 주어야하는데...그럼에도
// 경우의 수가 너무 많다. 
// 혹은 진행과정을 visit으로 찍어야하는데, 심한경우 10만개의 이동이 있는 경우도 있으므로,
// 메모리가 버텨주지 못한다.

//결국 bfs방식.. visit 방문 들른순간은 항상 최단이기때문에 이미 방문했던곳을 무시할수 있다.

//메모리를 아끼기 위해서 연산할떄는 vector queue 저장할때는 int형으로 저장.
// 함수를 두어 vector와 int 자료형을 convert

map<int, bool> visit;
struct Q {
	int v;
	int pos;
	int cnt;
};

//시작하는 0 자리.
int src = 0;
queue <Q> q;
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };

//일차원 벡터로 펼쳤을때, 2차원 공간 my,mx로 이동했을때 일차원 좌표
int move(int src, int my, int mx) {
	int y = src / 3 + my; int x = src % 3 + mx;
	if (y < 0 || y >2 || x < 0 || x > 2) return -1;
	return y * 3 + x;
}

//vector to int
int vtoi(vector<char> v) {
	int in = 0;
	for (int i = 0; i < 9; i++) {
		in = in * 10 + v[i];
	}
	return in;
}

//int to vector
vector<char> itov(int in) {
	vector<char> v(9);
	for (int i = 8; i >= 0; i--) {
		v[i] = in % 10; in /= 10;
	}
	return v;
}


int bfs(int start) {
	//목표 int
	int target = 123456780;
	visit[src] = true;
	q.push({ src,start,0 });

	while (!q.empty()) {
		//q정보 pop
		int cur = q.front().v; int pos = q.front().pos; int cnt = q.front().cnt; q.pop();
		
		if (cur == target) return cnt;

		//상하 좌우 이동.
		for (int i = 0; i < 4; i++) {
			int npos = move(pos, dy[i], dx[i]);
			if (npos == -1) continue; //범위 이탈
            
			vector<char> vtemp = itov(cur);
			swap(vtemp[pos], vtemp[npos]);
			int temp = vtoi(vtemp);
            
            //처음 방문하는 맵 상태이면 push
			if (!visit.count(temp)) {
				visit[temp] = true;
				q.push({ temp,npos,cnt + 1 });
			}
		}
	}
    //target으로 갈 수 있는 경우의 수가 존재 하지 않음
	return -1;
}
int main() {
	int start;
	int N;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> N;
			if (N == 0) start = i * 3 + j;
			src = src * 10 + N;
		}
	}

	cout << bfs(start);

}

 

PS.

DFS가 BFS보다 유리한 경우는 DFS와 BFS가 한단계씩 전진한다 표현하면,

BFS는 한단계에 갈수 있는 모든 경우의 수를 다 들리고 그다음 단계로 넘어가는 스타일이고,

DFS는 일단 끝까지 갈 수 있는 끝단계까지는 쭉 갔다. 다시 한단계씩만 뒤로 돌아와, 다음 경우의 수를 찾는 스타일이다.

 

만약 우리가 찾을 정답의 단계가 정해져있거나, 일반적으로 깊은 단계, 일정한 단계에 있는 문제라면,

DFS가 유리하다. 

단계까지 내려간 것중 정답이 되는 경우의 수는 현저하게 적을텐데

BFS는 한단계마다 매번 모든 경우의 수를 찾으므로,

한 경우의 수씩 살피다 찾으면 끝내버리는 DFS보다 일반적으로 느려질 수 있다.

 

예시로, 5단계까지 가야 값을 얻어 낼 수 있는 문제가 있고 그중 최적의 경우를 찾는다 하자.

DFS는 처음 5단계까지간 경우의 수에서 값 a를 얻었다.

그 후로는 몇단계까지 가던, a보다 커지는 값은 backtracking을 할 수 있게된다.

 

하지만 BFS는 4단계까지 갔을때 조차 아직 값을 얻어내지 못했고, 모든 경우의 수를 4단계까지 펼치면서 왔기때문에

DFS보다 느릴 가능성이 매우 크다. 

 

메모리 적으로도, BFS는 모든 결과가 마지막 단계에 도달해야만 한번에 나오므로 그전까지 저장하고 있어야하고,

DFS는 한번에 끝단계를 간후 결과를 보고나면 메모리를 반환할수 있다는 점에서도 차이가 있다.

 

DFS는 stack의 성질을 가지므로

순서대로 경우의 수 세기, 재귀적 성질을 이용한 쉬운 코딩의 장점이 있다.

 

요약!

 

최단 단계를 구하는 문제하면 BFS

 

가야하는 단계가 정해져있거나 일정하고

단계를 모두 완수했을때 최적의 값을 찾는다면 DFS!

 

속도,메모리, 구현의 난이도 문제는 있지만

대부분의 경우 DFS로 짠코드는 BFS로도 가능하다.

 

하지만 DFS는 단계가 끝나지 않는 순환의 문제가 생길 수 있고,

현재 찾은 정답이, 최단이라고 확정지을 수 없으므로, 계속 나머지 경우의 수를

세주어야 한다. 하지만, 이 과정에서 순환에 빠지게된다면 정답을 구할 수 없다.

 

보통 최단의 문제를 DFS로 구현하는 것은 불가능하거나

순환에 빠지지 않게 내가 visit으로 체크하는 상태를 더욱 세밀하게 만들경우 특정 문제는

상태 자체가 N! 경우의 수가 나올만큼 매우 어려워 질 수 있다.

 

예로, 현재 위치가 최단으로 도착했다는 보장을 할 수 없기에, 지금까지 달려온 경로 자체를 상태로 하게된다면,

적어도 경로가 같아야 같은 상태이므로 순환에 빠지는 일은 현저히 줄거나 제거할 수 있지만,

상태 자체를 현재 위치가 아닌 경로로 하게되면, visit을 찍어야되는 경우의 수가 급격히 늘어나는 것을 직관적으로도 알 수 있고, 메모리 적으로도 결국 BFS 보다 좋은 이점을 가질 수 없게된다.