[Algorithm] Baekjoon 1525번 : 퍼즐

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

1525번: 퍼즐

struct Node
{
    string s;
    int zeroY;
    int zeroX;
    int count;
};
 
int arr[3][3];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
string start;
int sZeroY;
int sZeroX;
string result = "123456780";
unordered_map<string, bool> visited;
 
bool isInRange(int y, int x)
{
    if (y < 0 || y >= 3 || x < 0 || x >= 3) return false;
    return true;
}
 
void BFS()
{
    queue<Node> q;
    q.push({ start,sZeroY,sZeroX,0 });
    visited[start] = true;
 
    while (!q.empty())
    {
        string cur = q.front().s;
        int curZeroY = q.front().zeroY;
        int curZeroX = q.front().zeroX;
        int curCount = q.front().count;
        q.pop();
 
        if (cur == result)
        {
            cout << curCount;
            return;
        }
 
        int curZeroIndex = 3 * curZeroY + curZeroX; // 0 ~ 8
 
        for (int i = 0; i < 4; ++i)
        {
            int nextZeroY = curZeroY + dir[i][0];
            int nextZeroX = curZeroX + dir[i][1];
 
            if (!isInRange(nextZeroY, nextZeroX)) continue;
 
            int nextZeroIndex = 3 * nextZeroY + nextZeroX;
 
            string nextS = cur;
            char temp = nextS[nextZeroIndex];
            nextS[nextZeroIndex] = '0';
            nextS[curZeroIndex] = temp;
 
            if (visited[nextS]) continue;
 
            visited[nextS] = true;
            q.push({ nextS,nextZeroY,nextZeroX,curCount + 1 });
        }
    }
 
    cout << -1;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            cin >> arr[i][j];
            start += arr[i][j] + '0';
 
            if (arr[i][j] == 0)
            {
                sZeroY = i;
                sZeroX = j;
            }
        }
    }
 
    BFS();
}

퍼즐판을 string으로 바꿔서 해쉬로 방문체크하는게 포인트다.

매 로직마다 0의 위치를 그때마다 찾는것보다는 (최대 9번씩 반복해야하니까) 그냥 노드에 0의 위치를 계속 넘겨주는걸 택했다.

빈칸을 기준으로 퍼져나가는데, 각방향마다 빈칸위치를 바꿨을 때의 퍼즐판형태, 즉 string을 key값으로 방문체크해주면 된다.

문제에서 무조건 1칸씩 1의 가중치로 이동한다면, 반드시 목표지점에 도착한순간이 최소값이라는게 보장된다.

그게 BFS다.