[백준] 1525 퍼즐

백준 1525 퍼즐 문제 풀이입니다.

퍼즐

이 문제는 bfs문제긴 한데 기존 문제들과 가장 큰 차이점은 이전 맵 정보를 매순간 기억해야한다는 점이였습니다.

그래서 전 어떻게 보관을 할지 고민하던 중 알고리즘 분류에 비트마스킹이 있는 것을 보고 어처피 3*3 배열이라면 축소가 가능하지 않을까 해서 배열을 string으로 줄여서 풀이를 해봤습니다.

1 0 3
4 2 5
7 8 6

이런 배열을 위 행부터 차례대로 string으로 변환한다면

103425786이 됩니다.

이 string을 queue에 넣고 bfs를 돌리면 됩니다. 단, 여기서 방문한 곳을 처리해야 하기 때문에 전 map<string,int> 를 사용해서 관리하였습니다. -> 이렇게 된다면 그 순간 string 즉 map상태가 저장되기 때문입니다. 또한, 중복 관리도 됩니다.

또, string을 3*3 배열로 만든 뒤 x,y좌표를 찾아야 하기 때문에 ‘0’이 위치하는 곳에 순서를 가져와서 그 값을 3으로 나누면 x좌표가 되고 3으로 나눈 나머지는 y좌표가 됩니다.

이렇게 풀게 된다면 결국 기존 bfs문제가 같아지게 됩니다.

소스코드는 다음과 같습니다.

Source Code:

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

map<string, int> visit;
int Answer;

#define TARGET "123456780"

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

int main() {
	string start = "";

	for (int i = 0; i < 9; i++) {
		int number;
		cin >> number;

		start += number + '0';
	}

	queue<pair<string,int>> q;
	q.push({ start,0 });
	visit[start] = 1;
	

	while (!q.empty()) {
		string cur = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (cur == TARGET) {
			Answer = cnt;
			break;
		}
		int blank = cur.find('0');

		int x = blank / 3;
		int y = blank % 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 next = cur;
			swap(next[blank], next[nx * 3 + ny]);

			if (!visit[next]) {
				visit[next] = 1;
				q.push({ next,cnt + 1 });
			}
		}
	}

	if (!visit[TARGET])
		cout << -1;
	else
		cout << Answer;



	system("pause");
	return 0;
}

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 문제 이해력 높히기….