[백준문제풀이] 1525 퍼즐

 

풀이일시 : 2020-11-14

​

 

문제 :

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

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

 

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

​

​

입력 :

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

ex)

1 0 3

4 2 5

7 8 6

​

​

출력 :

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

ex)

3

​

​

풀이 :

- 입력을 int 2차원배열이 아닌 문자열로 처리할것이다.

- 문자열로 처리하게 되면 정답문자열은 123456780 이 될 것이고 swap 하면서 찾아내게 될 것이다.

- 0의 인덱스를 찾은 후에 상하좌우의 값을 바꾸는(swap) bfs를 실행하며 찾을것이다.

- 한번 거쳐간 문자열의 방문확인을 위해 set 을 사용한다.

​

> string - find의 사용

- string a="12345"에서 a.find('2') 하면 2의 위치인 1이 반환될 것이다. 즉 인덱스번호가 반환됨

​

dbstndi6316.tistory.com/63

[기본문제풀이] BFS 너비우선탐색

 

#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <algorithm> //swap 사용위해
using namespace std;

string Start, End;
set<string> visit; //visit을 set화 시키기 위해 set 사용

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

int bfs() {
	queue<pair<string, int>> q;
	q.push({ Start,0 }); //start, cnt
	visit.insert(Start); //방문확인위해 넣는다.
	while (q.empty() == 0) {
		string cur = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (cur == End)
			return cnt;
		int zero = cur.find('0'); //0의 인덱스를 찾는다.
		int x = zero / 3; //0의 인덱스의 x값
		int y = zero % 3; //0의 인덱스의 y값
		for (int i = 0; i < 4; i++) { //0의 상하좌우 보기위해
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < 3 && ny < 3) { //범위
				string next = cur;
				swap(next[x * 3 + y], next[nx * 3 + ny]); //일렬로 펼쳐서 swap
				if (visit.find(next) == visit.end()) { //같은문자열이 없다면 (즉.end()라면)
					visit.insert(next); //삽입하기
					q.push({ next, cnt + 1 }); //cnt를 증가시켜 큐에넣기
				}
			}
		}
	}
	return -1;
}

int main() {

	End = "123456780"; //목표치
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			int a;
			cin >> a;
			char Tmp = a + '0'; //숫자들어온거에 '0'을 붙여 문자화
			Start = Start + Tmp; //start를 생성해준다.
		}
	}
	cout << bfs() << endl;
	return 0;
}