백준 1525 퍼즐

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 퍼즐을 이동시켜 123/456/780 의 형태로 만드는 최소의 이동횟수를 구하는 문제입니다. 2차원 배열로 생각하면 검사 조건이 까다롭기 때문에 이를 문자열로 생각하고 bfs를 통하여 해결을 하였습니다. 

 

우선 문자열을 입력받고 그 문자열을 큐에다가 넣습니다. 그리고 상하좌우 이동을 하여야 하는데 문자열의 인덱스를 기준으로 생각하면 좌우는 +1,-1이 되고 상하는 +3,-3이 되는 것을 알 수 있습니다. 

따라서 이 조건에 의해 문자열 안에 두 문자를 swap시킨뒤 문자열을 set에 넣었습니다. 그리고 그 문자열이 이전에 set에 들어온적이 있는지 검사를 한뒤 들어오지 않았다면 큐와 set에 각각 넣어준뒤 계속해서 bfs를 진행합니다.

각 단계별로 큐의 사이즈를 len변수에 넣어 진행한뒤 이동 횟수를 순차적으로 증가시켜주며 가장먼저 문자열이 123456780이 완성되었을때 함수를 종료시키면 최소 이동 횟수를 구할 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <queue>
#include <string>
#include <set>
#include <cstdio>

using namespace std;

string puzzle;
int nextx[4] = {-1,1,-3,3}; 
queue<string> q;
int num;
set<string> s;
bool flag = true;

void bfs() {
	int a;
	q.push(puzzle);
	s.insert(puzzle);
		
	while(!q.empty()) {
		
		int len = q.size();
		for(int j = 0; j < len; j++) {
		
		if(q.front() == "123456780") {
			flag = false;
			return;
		}
		
		for(int i = 0; i < 9; i++)
			if((q.front())[i] == '0') {
				a = i;
				break;
			}
		
		for(int i = 0; i < 4; i++) {
			int x = a + nextx[i];
			
			if (x < 0 || (a % 3 == 0 && i == 0) || (a % 3 == 2 && i == 1) || x >= 9) // 범위를 벗어난 조건 
				continue;			
			
			else {
				string cp = q.front(); //문자열 swap 
				swap(cp[x], cp[a]);
				if (s.count(cp) == 0) {
					s.insert(cp);	
					q.push(cp);
				}
			}
		}
		
		q.pop();
	}
		num++;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	for(int i = 0; i < 9; i++) {
		char a;
		cin >> a;
		puzzle += a;
	}
	
	bfs();
	if(flag) //flag가 true이면 문자열이 완성되지 못한경우 
		cout << -1;
	else
		cout <<num;
	return 0;
}