[백준/C++/BFS] 1525번 퍼즐

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

1525번: 퍼즐

문제

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으로 나타낸다.

 

출력

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

---

BFS 문제를 해결 할때면 항상 데이터를 이차원 배열이나 pair<int,int> 형식으로 저장하려고 했다. 이 문제도 그런 방식으로 해결하려다 보니 도저히 방법이 떠오르지 않아 다른 풀이를 참고하여 해결하였다. 이번에는 set자료구조를 이용해 3X3 배열에 변동이 생길때마다 set자료구조에 저장하여 다음 0이 옮기는 위치와 비교해주는 BFS방식으로 해결 한 문제입니다.

while(!q.empty())
    {
        string now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        if(now == "123456780" && (answer == -1|| answer>cnt))
            answer = cnt;
        
        int zero = now.find('0');
        int x = zero/3, y = zero%3; //0부터 8까지라서 나눈게 x즉 가로, 나머지가 세로
        
        for(int i=0;i<4;i++)
        {
            int ny = y + dir[i][0];
            int nx = x + dir[i][1];
            
            if(ny<0||ny>=n||nx<0||nx>=n)
                continue;
            string ns = now;
            swap(ns[x*3+y], ns[nx*3+ny]); //원래의 위치
            
            if(check.find(ns)==check.end()) //같지 않으면 push find()가 못찾으면 end()
            {
                check.insert(ns);
                q.push({ns,cnt+1});
            }
        }
    }

now에 해당하는 문자열이 우리가 찾고자하는 문자인 "123456780"으로 정렬되었을때 answer 를 cnt값으로 바꾼다. 큐가 비어 있을때 까지는 반복을 하지만 맨 처음 으로 answer값이 바뀌었을떄가 가장 최솟값이니 if()문제 (answer == -1 || answer>cnt) 조건을 넣어주어 최솟값외의 값이 들어가는 것을 방지한다.

 

1. swap 함수를 이용해 0의 위치와 그 주변에 4곳의 위치를 바꾸어 줍니다.

2. set자료구조에 find 함수를 이용해 요소가 존재하지 않으면 end()를 반환하기 떄문에 그 점을 이용해 요소가 존재하지 않다면 큐에 새로운 3X3행렬을 집어넣고 cnt를 1 증가시켜줍니다.

 

전체소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>
#include <string>
using namespace std;

const int n = 3;
string start = "";
int answer = -1;



int main()
{
    int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    int answer = -1;
    queue<pair<string,int>>q;
    set<string>check;
    string s = "";
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            char x;
            cin>>x;
            s+=x;
        }
    }
    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" && (answer == -1|| answer>cnt))
            answer = cnt;
        
        int zero = now.find('0');
        int x = zero/3, y = zero%3; //0부터 8까지라서 나눈게 x즉 가로, 나머지가 세로
        
        for(int i=0;i<4;i++)
        {
            int ny = y + dir[i][0];
            int nx = x + dir[i][1];
            
            if(ny<0||ny>=n||nx<0||nx>=n)
                continue;
            string ns = now;
            swap(ns[x*3+y], ns[nx*3+ny]); //원래의 위치
            
            if(check.find(ns)==check.end()) //같지 않으면 push find()가 못찾으면 end()
            {
                check.insert(ns);
                q.push({ns,cnt+1});
            }
        }
    }
    cout<<answer<<endl;
    

}

같은 BFS문제라도 문제 성격에 따라 자료를 저장하는 방식과 자료를 다루는 것에서 부터 문제 접근의 난이도 차이가 많이 나는 것을 느꼈고, 해결하려는 문제에 따라 적절하게 자료를 이용하는 것이 중요하다는 것을 배우게 된 문제였습니다.