백준 1525 퍼즐

문제 설명

3 X 3 슬라이딩 퍼즐을 움직여 원래대로 맞추는 문제.

해결 방법

그냥 int 배열을 queue에 저장하여 풀었더니 메모리 초과가 나서 다른 사람의 풀이를 보고 아이디어를 얻었다.
int 배열이 아니라 "1234567890" 식의 문자열을 이용하여 저장하는것이 포인트.
그리고 set을 이용하여 새로운 문자열만 queue에 넣어줘서 반복을 피한다.

---

	for(int i=0;i<9;i++){
		scanf(" %c",&c);
		s1+=c;
	}
	s.insert(s1);
	q.push(make_pair(s1,0));

맨 처음 퍼즐을 받을때부터 빈 문자열을 생성한 후 하나씩 넣어준다.
그리고 문자열을 time과 함께 pair로 넣어주고 동시에 queue에도 넣어준다.

---

s1+=c;

string은 이런식의 char형 덧셈 연산이 가능하다.

---

	while(!q.empty()){
		if(q.front().first=="123456780"){
			printf("%d",q.front().second);
			return 0;
		}
		int zero= q.front().first.find('0');
		int x=zero/3;  //행 좌표
		int y = zero%3; //열 좌표
		for(int i=0;i<4;i++){
			int xx=x+_x[i];
			int yy=y+_y[i];
			if(xx>=0&&xx<3&&yy>=0&&yy<3){
				string s2 = q.front().first;
				swap(s2[zero],s2[xx*3+yy]);

				if(s.find(s2)==s.end()){
					s.insert(s2);
					q.push(make_pair(s2,q.front().second+1));

				}
			}
		}
		q.pop();
	}

find를 이용해 0의 위치를 찾아준 후 상하좌우로 가능한 위치를 찾아 바뀐 문자열을 만들어준다.

---

if(s.find(s2)==s.end()){
	s.insert(s2);
    q.push(make_pair(s2,q.front().second+1));
}

set안에 존재하는지 확인한 후 (존재하지 않으면 s.end()를 리턴)
존재하지 않으면 set과 queue에 넣어준다.

코드

#include <stdio.h>
#include <string.h>
#include <set>
#include <queue>
#include <iostream>
#include <string>

int _x[4]={-1,1,0,0};
int _y[4]={0,0,-1,1};

using namespace std;
set<string> s;
queue<pair<string,int> > q;

int main(){
	string s1 = "";
	char c;
	for(int i=0;i<9;i++){
		scanf(" %c",&c);
		s1+=c;
	}
	s.insert(s1);
	q.push(make_pair(s1,0));
	
	while(!q.empty()){
		if(q.front().first=="123456780"){
			printf("%d",q.front().second);
			return 0;
		}
		int zero= q.front().first.find('0');
		int x=zero/3;
		int y = zero%3;
		for(int i=0;i<4;i++){
			int xx=x+_x[i];
			int yy=y+_y[i];
			if(xx>=0&&xx<3&&yy>=0&&yy<3){
				string s2 = q.front().first;
				swap(s2[zero],s2[xx*3+yy]);

				if(s.find(s2)==s.end()){
					s.insert(s2);
					q.push(make_pair(s2,q.front().second+1));

				}
			}
		}
		q.pop();
	}
	printf("-1");
}