백준 1525 - 퍼즐

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

힌트

필요한 것: string

가능한 경우의 수: 9!

풀이

한 군데가 비어있는 퍼즐을 오름차순으로 배치하는 최소 횟수를 찾는 문제다.

 

비어있는 위치를 9라고 하면

 

1 2 3

4 5 6

7 8 9

 

의 형태로 퍼즐을 만드는 문제로 바꿀 수 있다.

 

그리고 이를 일렬로 나열하면 일직선 퍼즐을 123456789로 만드는 문제로 바꿀 수 있다.

 

퍼즐의 각 위치에서 이동할 수 있는 곳에 에지를 연결하면서 그래프 모델링을 하자.

 

그러면 현재 퍼즐의 상태가 주어졌을 때 숫자가 9인 노드는 연결된 노드의 숫자와 swap 할 수 있다는 의미가 된다.

 

123456789를 기준으로 9는 6, 8과 swap이 가능하다. 즉 9가 위치한 노드와 연결된 노드의 숫자를 서로 바꾸는 경우를 모두 탐색하면 최종 9! 의 경우의 수를 살펴보게 된다.

 

9! 의 경우는 그다지 큰 경우가 아니므로 BFS의 사용을 고려할 수 있다.

 

BFS를 어떻게 해야 하는지 고민이 있을 수 있는데 저렇게 일직선으로 바꾼 퍼즐을 스트링으로 처리하면 된다.

 

예제 TC1의 경우에는 "193425786"이 된다. 0을 9로 바꿨음을 잊지 말자.

 

그러면 BFS를 수행하는 큐에는 퍼즐의 상태를 나타내는 스트링이 들어가게 되며 각 원소마다 9가 위치한 노드와 연결된 노드들을 swap 해가며 최적의 경우를 탐색하면 된다.

 

각 상태에 도달하기 위한 최소 횟수를 map<string, int>로 관리할 수 있으며 count()가 false 거나 mp[current] + 1 < mp[next_string] 이면 이를 map에 반영, 큐에 삽입해서 간단하게 구현할 수 있다.

 

BFS가 끝난 뒤 map에 "123456789"가 존재하면 해당 value 출력, 없으면 -1을 출력하면 정답을 받을 수 있다,

 

자세한 구현은 밑 코드를 참조한다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, int> mp;
vector<int> graph[10];

void solve()
{
  string s("999999999");
  graph[1] = {2, 4};
  graph[2] = {1, 3, 5};
  graph[3] = {2, 6};
  graph[4] = {1, 5, 7};
  graph[5] = {2, 4, 6, 8};
  graph[6] = {3, 5, 9};
  graph[7] = {4, 8};
  graph[8] = {7, 5, 9};
  graph[9] = {6, 8};

  for (int i = 0; i < 9; ++i)
  {
    int x;
    cin >> x;
    if (x != 0) s[i] = x + '0';
  }

  mp[s] = 0;
  queue<string> q;
  q.push(s);

  while (q.size())
  {
    string cur = q.front();
    q.pop();

    int idx = cur.find("9");

    for (int i: graph[idx + 1])
    {
      string nxt = cur;

      swap(nxt[idx], nxt[i - 1]);

      if (!mp.count(nxt) || mp[nxt] > mp[cur] + 1)
      {
        mp[nxt] = mp[cur] + 1;
        q.push(nxt);
      }
    }
  }

  if (mp.count("123456789")) cout << mp["123456789"];
  else cout << -1;
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}

제출 기록

보너스

https://atcoder.jp/contests/abc224/tasks/abc224_d

D - 8 Puzzle on Graph

이것도 풀어보자.