개요

백준 1525: 퍼즐

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

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

접근 방식

1. 숫자와 9칸짜리 배열을 담는 구조체를 생성 후 구조체를 생성해 구현해보려했으나,
   방문배열을 어떻게 만들어야 되는지를 몰랐다.

2. 숫자 0~8에대한 방문배열이아니라 해당 문자열자체에 대해 방문 배열을 만들어줘야 하는 문제였다. 따라서 string형의 set자료구조를 활용해 해당 문자열을 방문했는지 안했는지 체크해줬다.

3. 0의 위치를 알아야하기때문에 전체 숫자열에해당하는 문자열과 0의 위치를 가지고 잇는 구조체를 선언하였다,

   struct puzzle {
   	int zeroLoc;
   	string puzzleArr;
   };

4. 이번에도 미리 배열을 상하좌우에 해당하는 {3,-3,-1,1}배열을 선언했으나
   문제는 이런식으로 만들면
   1 2 3
   4 5 6
   7 8 0
   이런 배열에서 6번자리의 숫자는 조사를 원래대로라면 3,5,0번을 해야하지만,
   3,-3,-1,1을 해버리면 3 5 7 0을 조사해버린다.
   따라서 경계에 있는지 체크해줘야했다.

   //반복문 일일히 코딩하기 귀찮아서 쓰는 배열
   int dx[4] = { -1,1,0,0 };
   int dy[4] = { 0,0,-1,1 };
   int dz[4] = {-3,3,-1,1};

5. 따라서 0이 있는 위치를 3으로 나눈 몫과 나머지를 이용해 (몫,나머지)좌표로 알아내서
   경계면인지 아닌지를 체크해줬다.

	//0좌표의 행
	int x = cur.zeroLoc / 3;
	//0좌표의 열
	int y = cur.zeroLoc % 3;
	for (int i = 0; i < 4; i++) {
		//0좌표의 다음 행값
		int nextX = x + dx[i];
		//0좌표의 다음 열값
		int nextY = y + dy[i];			
		//nextX nextY값이 범위 벗어나면 continue (현재 0위치가 경계면이면 
        //3개의 값만 조사해야되는데 4개의 값 조사하는걸 막는다.)
		if (nextX < 0 || nextY<0 || nextX/3>=1 || nextY/3>=1) continue;
        //다음 zero값과 zero 바꿔준다.
		swap(cur.puzzleArr[cur.zeroLoc+dz[i]], cur.puzzleArr[cur.zeroLoc]);

코드

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

string target = "123456780";
//방문 배열은 첨에 생각했던거처럼 1 2 3 숫자에대해 체크가 아니라 문자열에대해 체크 
//해당 문자열을 시도했냐 안했냐로
set<string> visited;
//반복문 일일히 코딩하기 귀찮아서 쓰는 배열
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int dz[4] = {-3,3,-1,1};

struct puzzle {
	int zeroLoc;
	string puzzleArr;
};

queue<puzzle> q;

void Input() {
	string init="";
	int tmp = 0;
	int zero = 0;
	for (int i = 0; i < 9; i++) {
		cin >> tmp;
		//string 값으로 받아서 비교하자
		init += tmp + '0';
		//0위치 기록
		if (tmp == 0) zero = i;
	}
	//큐에 푸시
	q.push({zero,init});
	//방문 set에 넣어준다.
	visited.insert(init);
}
void Solution() {
	if (q.front().puzzleArr == target) {
		cout << 0;
		return;
	}
	int level = 1;
	for (; !q.empty();level++) {
		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			puzzle cur = q.front();
			q.pop();
			//0좌표의 행
			int x = cur.zeroLoc / 3;
			//0좌표의 열
			int y = cur.zeroLoc % 3;

			for (int i = 0; i < 4; i++) {
				//0좌표의 다음 행값
				int nextX = x + dx[i];
				//0좌표의 다음 열값
				int nextY = y + dy[i];
				
				//nextX nextY값이 범위 벗어나면 continue (현재 0위치가 경계면이면 3개의 값만 조사해야되는데 4개의 값 조사하는걸 막는다.)
				if (nextX < 0 || nextY<0 || nextX/3>=1 || nextY/3>=1) continue;
				//다음 zero값과 zero 바꿔준다.
				swap(cur.puzzleArr[cur.zeroLoc+dz[i]], cur.puzzleArr[cur.zeroLoc]);
				//cur값이 답이되면 level 출력
				if (cur.puzzleArr == target) {
					cout << level;
					return;
				}
				//cur 처음보는 배열이면 set과 queue에 추가
				if (visited.find(cur.puzzleArr) == visited.end()) {
					visited.insert(cur.puzzleArr);
					q.push({ cur.zeroLoc+dz[i],cur.puzzleArr });
				}
				//cur을 반복문에서 계속 쓰이므로 되돌려놓기
				swap(cur.puzzleArr[cur.zeroLoc + dz[i]], cur.puzzleArr[cur.zeroLoc]);

			}
		}

	}
	cout << -1;

}

int main() {
	Input();
	Solution();
}

문풀후생

일단 방문배열을 문자열을 담은 set자료구조로 하여 해당 배열을 방문했는지 체크하는 부분을 배웠고,
경계면에서 3개의 값만 체크해야 하는 걸 배웠던 문제다.