백준 1525: 퍼즐

퍼즐 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

32 MB (하단 참고)

13432

5774

3551

41.479%

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

예제 입력 1 복사

1 0 3
4 2 5
7 8 6

예제 출력 1 복사

3

예제 입력 2 복사

3 6 0
8 1 2
7 4 5

예제 출력 2 복사

-1

 

#include<iostream>
#include<string>
#include<set>
#include<queue>
using namespace std;

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int main() {
	int answer = -1;
	string s;
	set<string> SET;
	queue<pair<string, int>> q;
	for (int i = 0; i < 9; i++) {
		char c;
		cin >> c;
		s += c;
	}
	q.push({ s,0 });
	SET.insert(s);

	while (!q.empty()) {
		string k = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (k == "123456780" && (cnt < answer || answer == -1))
			answer = cnt;
		int zero = k.find('0');
		int x = zero / 3, y = zero % 3;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3)continue;
			string ns = k;
			swap(ns[x * 3 + y], ns[nx * 3 + ny]);
			
			if (SET.find(ns) == SET.end()) {
				SET.insert(ns);
				q.push({ ns,cnt + 1 });
			}
		}
	}
	cout << answer;

	return 0;
}

풀이법을 떠올리기 힘든 문제다!