퍼즐

www.acmicpc.net/problem/1525

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	173282	49633	31180	25.184%

문제

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

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다.

물론 표 바깥으로 나가는 경우는 불가능하다.

우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다.

다음의 예를 보자.

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다.

이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다.

한 줄에 세 개의 수가 주어지며, 빈 칸은 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

출처

• 문제를 번역한 사람: baekjoon
• 잘못된 데이터를 찾은 사람: djm03178
• 데이터를 추가한 사람: hello70825
• 메모리 제한을 수정한 사람: portableangel

알고리즘 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

메모리 제한

• Java 8: 256 MB
• Java 8 (OpenJDK): 256 MB
• Java 11: 256 MB
• Kotlin (JVM): 256 MB

---

시간 초과 및 메모리 초과로 고통 받은 문제

메모리의 제한으로 배열보다 string 값으로 퍼즐을 표현한 것이 이 문제의 포인트 같다.

통과된 코드 (BFS)

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

using namespace std;

string puzzle; // 퍼즐의 상태를 저장할 변수

queue<pair<string, int>> myqueue;
// 퍼즐의 초기상태와 실행 횟수를 넣어줌
// 탐색 시 상 / 하 / 좌 / 우 움직임 정의

set<string> checkset;
// 상태가 중복되는 것을 허용하지 않게 만듬(최단거리를 계산해준다.)
// 같은 값을 넣어도 하나만 존재

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

int result = -1;

void BfsAndCheck()
{
	myqueue.push({puzzle, 0});
	checkset.insert(puzzle);
	
	while (!myqueue.empty())
	{

		string currentString = myqueue.front().first;
		int countTry = myqueue.front().second;
		myqueue.pop();



		if (currentString == "123456780" &&(result == -1 || result > countTry))
		{
			result = countTry;
		}

		int zeroPos = currentString.find('0'); //  0의 위치찾고 반복자를 찾음

		// 인덱스 값으로 행과 열의 값을 가져온다.
		int x = zeroPos / 3;
		int y = zeroPos % 3;


		// 해당 위치에서 상 하 좌 우 4가지 방향으로 자리를 바꾸면서 큐에 넣어준다. 
		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 next = currentString;
			//   현위치, 다음 위치를 바꿈
			swap(next[x * 3 + y], next[nx * 3 + ny]);

			// 방문한 경험이 있는지 확인
			if (checkset.count(next) == 0)
			{
				checkset.insert(next);
				myqueue.push({ next, countTry + 1 });
			}
		}
	}
}

// 값을 입력받아 퍼즐을 셋팅
void Init()
{
	char temp;
	for (int i = 0; i < 9; i++)
	{
		cin >> temp;
		puzzle.push_back(temp); // 문자열의 맨 끝에 추가
	}
}

int main()
{
	Init();
	BfsAndCheck();
	//cout << ANSWER << "\n" << puzzle;
	cout << result;
	return 0;
}