백준 1525 - 퍼즐(C++, 복습)

문제 링크입니다 https://www.acmicpc.net/problem/1525

1525번: 퍼즐

출력 예시

123 / 456 / 780의 순서로 퍼즐을 만들면 되는 문제였습니다.

이때 0을 1~8 이외의 숫자인 9로 정해준뒤 이동시키는 문제였습니다.

따라서 123456789의 순서로 만들어주면 됩니다. -> 123 / 456 / 789

9를 가진 칸은 비어있음을 의미함으로 해당 위치에서 4방향 탐색을 통해서 이동할 수 있는 곳으로 이동합니다.

3*3 배열이기에 위의 과정을 전부 확인해봅니다(브루트 포스)

이동하는 과정에서 123456789의 순서로 나열되는 것이 있다면? -> 해당 퍼즐은 만들 수 있다

큐를 전부 확인했음에도 만들지 못했다면? -> 해당 퍼즐은 만들 수 없다

 

 

문제 접근 방법

1. 0을 9로 만들어주면서 퍼즐을 저장한다. 이때 시작점의 나열도 같이 계산해줍니다.

2. 9의 위치를 찾은 후에 해당 칸에서 4방향 탐색을 한다.

3. 이전에 방문하지 않은 곳이라면, 해당 지점을 방문했다고 해주면서 queue에 저장한다.

4. 2 ~ 3번 탐색 중, 123456789에 도달했다면 break해준다.

 

 

이전에 탐색한 곳을 저장할 때 배열을 사용한다면 크기가 약 1억개의 배열을 선언해야합니다. -> 메모리 부족

따라서 이때 map<int,int>라는 것을 사용해야합니다.

https://blockdmask.tistory.com/87

[C++] map container 정리 및 사용법

이분 블로그에서 map에 대해서 자세하게 나와있으니 읽어보고와주세요!

 

check를 map를 이용해 선언했을 때,

해당 칸에 값이 있는지를 판별하는 방법이 있습니다. -> check.count(x) -> x칸에 해당 값이 있으면 1, 아니면 0을 반환

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <string>

using namespace std;

int answer = 123456789;
int maps[3][3];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int start;

int bfs(int start) {
	queue<int> q;
	q.push(start);
	map<int, int> check;
	check[start] = 1;
	while (!q.empty()) {
		int num = q.front();
		string a = to_string(num);
		int start_find = 0;
		q.pop();
		if (num == answer) break;
		for (int i = 0; i < a.size(); i++) {
			if (a[i] == '9') {
				start_find = i;
				break;
			}
		}
		int x = start_find / 3;
		int y = start_find % 3;
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3) {
				string s = a;
				swap(s[xx * 3 + yy], s[x * 3 + y]);
				int new_ = stoi(s);
				if (check.count(new_) == 0) {
					check[new_] = check[num] + 1;
					q.push(new_);
				}
			}
		}
	}
	if (check.count(answer) == 1) {
		return check[answer] - 1;
	}
	else return -1;
}

void solve() {
	int ans = bfs(start);
	cout << ans;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> maps[i][j];
			if (maps[i][j] == 0) maps[i][j] = 9;
			start = start * 10 + maps[i][j];
		}
	}
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!