[ 백준 ] 1525번 - 퍼즐 ( C++ )

bfs문제 중 조금 어려운 수준에 속하는 문제다.

그동안 배열을 이용하면서 bfs를 수행했는데, 

이 문제는 배열의 인덱스끼리 서로 내용을 바꾸어야하는 점에서 풀이를 생각해내지 못했다.

상하좌우 모두 방문해야하는데, 그때마다 배열의 내용을 바꾸면 다음 방문에 영향을 끼치기 때문이다.

매 방문마다 바뀌는 배열을 모두 저장할 수도 없는 것이고.. 

그러면 어떻게 해야할까 생각을 하다가 풀지 못하고 다른 사람의 풀이를 참고하게 됐다.

배열이 아닌 간단하게 string을 쓰는게 흥미로웠다.

 

 

<문제>

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

1525번: 퍼즐

 

 

 

<참고해서 푼 풀이>

#include<bits/stdc++.h>
using namespace std;

int arr[3][3];

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
  int ans = -1;
  queue<pair<string,int>> q;
  set<string> check;
  
  string s = "";
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      char c;
      cin>>c;
      s += c;
    }
  }
  check.insert(s);
  q.push({s,0});

  while(!q.empty()){
    string now = q.front().first;
    int cnt = q.front().second;
    q.pop();
    
    if(now == "123456780" && (ans == -1 || ans > cnt))
      ans = cnt;
    
    int zero = now.find('0');
    int x = zero/3, y = zero%3;
    
    for(int i=0; i<4; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      
      if(nx<0 || nx>=3 || ny<0 || ny>=3) continue;
      string ns = now;
      swap(ns[x*3+y], ns[nx*3+ny]);
      
      if(check.find(ns) == check.end()){
        check.insert(ns);
        q.push({ns,cnt+1});
      }
    }
  }
  cout<<ans;
}

퍼즐을 배열이 아닌 string으로 저장하여 비교하면서 bfs를 실행했다. 

이렇게 하면 상하좌우 방문 시에 string 인덱스를 swap해서 넣을 수 있어서 간단하다.

방문여부는 set<string>으로 비교할 수 있다.

그리고 퍼즐이 다맞춰졌을때의 최소횟수를 저장한다.