백준 1525번: 퍼즐
퍼즐
아이디어
좀 어려운 BFS문제다. 우선 퍼즐을 표현할 때 문자열으로 표현했다. 2차원 배열로 표현하면 map의 key로 사용할 수 없기 때문이다.(근데 이거 포인터로 하면 될것같기도?… 잘 모르겠다.) 또 일반적으로는 visited 배열로 방문했음을 표시하지만 이번에는 map에 표시했다. key는 퍼즐 상태, value는 이동 횟수로 저장했다. 9!이라 1차원 배열 만들어서 표시해도 됐을거같은데 이렇게 풀면 4*4 퍼즐도 풀 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
map<string, int> m;
queue<string> q;
vector<string> get_boards(string str) {
vector<string> ret;
int zero = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '0') zero = i;
}
if (zero-3 >= 0) {
string s = str;
string c;
c += str[zero-3];
s.replace(zero-3, 1, "0");
s.replace(zero, 1, c);
ret.push_back(s);
}
if (zero%3 != 2) {
string s = str;
string c;
c += str[zero+1];
s.replace(zero+1, 1, "0");
s.replace(zero, 1, c);
ret.push_back(s);
}
if (zero%3 != 0) {
string s = str;
string c;
c += str[zero-1];
s.replace(zero-1, 1, "0");
s.replace(zero, 1, c);
ret.push_back(s);
}
if (zero+3 < 9) {
string s = str;
string c;
c += str[zero+3];
s.replace(zero+3, 1, "0");
s.replace(zero, 1, c);
ret.push_back(s);
}
return ret;
}
void bfs() {
while (!q.empty() && m["123456780"] == 0) {
string s = q.front();
q.pop();
vector<string> boards = get_boards(s);
for (auto x : boards) {
if (!m[x] || m[x] > m[s] + 1) {
m[x] = m[s] + 1;
q.push(x);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
char ch;
string input;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> ch;
input += ch;
}
}
m[input] = 1;
q.push(input);
bfs();
if (input == "123456780") cout << 0;
else cout << m["123456780"] - 1;
return 0;
}
여담
C++ 문자열 다루기 너무 힘들다. 파이썬 마렵다. 내가 더럽게 짠건가?
Author And Source
이 문제에 관하여(백준 1525번: 퍼즐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-1525번-퍼즐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)