C++ / 백준 / 1525 / 퍼즐

문제

https://www.acmicpc.net/problem/1525

1525번: 퍼즐

문제풀이

3x3퍼즐을 1차원 배열로 나타내고, visit를 set<vector<int>>로 만들었다.

퍼즐을 옮기고 해당 모양이 있는지 visit를 통해 확인을 하고, 없으면 visit에 해당 모양을 추가하고 큐에 push 했다.

visit에 이미 있으면 다음으로 넘어간다.

BFS를 통해 풀었고 단순하게 0의 위치에 따라 바꿀수 있는 경우를 모두 if, else if문을 써서 해결했다.

 

void CanPush(queue<pair<vector<int>, int>>& q, vector<int>puzzle, int num1, int num2, int cnt) {
	swap(puzzle[num1], puzzle[num2]);
	if (puzzle == answer) {
		cout << cnt + 1;
		exit(0);
	}
	else if (visit.find(puzzle) == visit.end()) {
		visit.insert(puzzle);
		q.push({ puzzle,cnt + 1 });
	}
}

num1, num2를 받아 서로 위치를 바꾼다.

바꾼것이 답인지를 체크하고 답이면 cnt+1을 하여 출력 후 종료,

답이 아니면 visit에 있는지 체크를 하고 없으면 insert 하고, q에 push를 한다.

BFS는 큐가 빌때까지 while문을 반복하였고, 만약 while문의 반복이 끝났는데도 답이 나오지 않았으면 해결할 수 없는 것이므로 -1을 출력한다.

 

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
set<vector<int>>visit;
vector<int>answer = { 1,2,3,4,5,6,7,8,0 };

void CanPush(queue<pair<vector<int>, int>>& q, vector<int>puzzle, int num1, int num2, int cnt) {
	swap(puzzle[num1], puzzle[num2]);
	if (puzzle == answer) {
		cout << cnt + 1;
		exit(0);
	}
	else if (visit.find(puzzle) == visit.end()) {
		visit.insert(puzzle);
		q.push({ puzzle,cnt + 1 });
	}
}

void BFS(vector<int>input) {
	queue<pair<vector<int>, int>>q;
	q.push({ input,0 });
	visit.insert(input);
	vector<int>puzzle;
	int cnt = 0;
	while (!q.empty()) {
		puzzle = q.front().first;
		cnt = q.front().second;
		q.pop();

		if (puzzle[0] == 0) {
			CanPush(q, puzzle, 1, 0, cnt);
			CanPush(q, puzzle, 3, 0, cnt);
		}
		else if (puzzle[1] == 0) {
			CanPush(q, puzzle, 0, 1, cnt);
			CanPush(q, puzzle, 4, 1, cnt);
			CanPush(q, puzzle, 2, 1, cnt);
		}
		else if (puzzle[2] == 0) {
			CanPush(q, puzzle, 1, 2, cnt);
			CanPush(q, puzzle, 5, 2, cnt);
		}
		else if (puzzle[3] == 0) {
			CanPush(q, puzzle, 0, 3, cnt);
			CanPush(q, puzzle, 4, 3, cnt);
			CanPush(q, puzzle, 6, 3, cnt);
		}
		else if (puzzle[4] == 0) {
			CanPush(q, puzzle, 1, 4, cnt);
			CanPush(q, puzzle, 3, 4, cnt);
			CanPush(q, puzzle, 5, 4, cnt);
			CanPush(q, puzzle, 7, 4, cnt);
		}
		else if (puzzle[5] == 0) {
			CanPush(q, puzzle, 2, 5, cnt);
			CanPush(q, puzzle, 4, 5, cnt);
			CanPush(q, puzzle, 8, 5, cnt);
		}
		else if (puzzle[6] == 0) {
			CanPush(q, puzzle, 3, 6, cnt);
			CanPush(q, puzzle, 7, 6, cnt);
		}
		else if (puzzle[7] == 0) {
			CanPush(q, puzzle, 4, 7, cnt);
			CanPush(q, puzzle, 6, 7, cnt);
			CanPush(q, puzzle, 8, 7, cnt);
		}
		else if (puzzle[8] == 0) {
			CanPush(q, puzzle, 5, 8, cnt);
			CanPush(q, puzzle, 7, 8, cnt);
		}
	}
	cout << "-1";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int idx = 0;
	vector<int>puzzle(9, 0);
	for (idx = 0; idx < 9; ++idx)
		cin >> puzzle[idx];
	if (puzzle == answer) cout << "0";
	else BFS(puzzle);
}