백준 1525 퍼즐

<링크>

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

<소스코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include<stdio.h> #include<queue> #include<set> #include<string> #include<iostream> using namespace std; queue<string> q; set<int> isVisited; int to[4] = { -1,1,-3,3 }; int bfs(string); int main() {     string start;     int n;     for (int i = 0; i < 9; ++i) {         scanf("%d", &n);         start += n + '0';     }     printf("%d",bfs(start));   } int bfs(string s) {     int depth = 0;     q.push(s);     isVisited.insert(stoi(s));     while (!q.empty())     {         int size = q.size();         for (int i = 0; i < size; ++i)         {             string cur = q.front();             q.pop();             if (cur.compare("123456780")==0)                 return depth;               int zero;             for (int j = 0; j < 9; ++j) //0의위치를 알아내고                 if (cur[j] == '0')                 {                     zero = j; break;                 }             for (int j = 0; j < 4; ++j)             {                 if (j < 2)                     if ((zero + to[j]) / 3 != zero / 3) continue;                 if (zero + to[j] >= 0 && zero + to[j] < 9)                 {                                         string toStr = string(cur);                     swap(toStr[zero + to[j]], toStr[zero]);                     int toNum = stoi(toStr);                     if (isVisited.find(toNum) == isVisited.end())                     {                         isVisited.insert(toNum);                         q.push(toStr);                     }                 }             }         }         ++depth;     }     return -1; } Colored by Color Scripter

cs

<풀이>

1. 방문했는지 안했는지 여부를 set을 이용해 구현했다. 판때기에 있는 숫자들을 한줄로 쫙 깐다음에 하나의 정수로 표현한다.

1 2 3
4 5 6
7 8 0
: 123456780

0 1 3
2 4 6
5 8 7
: 13246587

2. 하나의 노드는 string으로 표현했다.

3. string상에서 '0'의 위치를 찾아내고 그 상하좌우에 있는 수와 자리를 바꾼뒤, bfs를 이어간다.

상,하는 -3, +3을 하면 된다.

좌,우는 -1, +1을 하되, 같은 라인에 있는지 확인해야한다.

index / 3이 같으면 같은 라인에 있는것이다.

string상에서의 인덱스 : 012345678 

판떼기 상에서의 인덱스 :
012 : /3 =0
345 : /3 =1
678 : /3 =2

4. java 라이브러리를 통해 구현한다면

HashSet의 contains메소드를 쓰면될것같다.