[그래프] HANOI4 하노이의 네 탑

1. 문제

 

기둥이 4개가 있다.

 

네 개의 기둥에 원반들이 자유롭게 배치되어있을 때 (작은것이 위로 와야함)

 

모든 원반을 맨 오른쪽 기둥으로 옮겨 놓기 위해 필요한 최소한의 움직임 수를 계산하는 프로그램을 작성하여라

 

 

 

2. 최소거리 탐색

 

기둥이 4개, 원반이 최대 12개 이므로

 

기둥은 2비트로 표현가능하므로

 

각 원반마다 해당하는 기둥을 나타내는 상태공간은 최대 24비트만 있으면 표현가능하다.

 

 

상태공간에서 최단거리를 구하기위해 너비우선 탐색을 사용하면 시간이 초과 될 수 있다.

 

분기점은 최대 6개에 최소 3개이니 대략 5라고하자

 

그러면 최단거리가 d일때  O(5^d) 의 시간이 걸린다.

 

 

하지만 목표상태에서 역방향으로 움직이기 쉬우므로 양방향 탐색을 통해 시간을 줄일 수 있다. 

 

그러면  O(5^(d/2))로 어느정도 시간을 줄일 수 있다. 

 

 

다음은 비트마스크로 상태를 표현한 양방향 탐색을 구현한 코드이다.

 

 

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
int N;
int d[1<<24];
int getPos(int i, int ring) 
{
  return (ring>>(2*(i-1))) & 3;   
}
int setPos(int _ring, int i, int pos)
{
  return (_ring & ~(3<<((i-1)*2))) | (pos<<((i - 1) * 2));  
}
int bitMask(vector<vector<int> >& r) 
{
  int ring = 0;
  
  for(int i = 0; i < r.size(); i++) 
  {
    for(int j = 0; j < r[i].size(); j++)
      ring = setPos(ring, r[i][j], i);
  }
  return ring;
}    
vector<int> getAdjacent(int _ring){
  vector<int> adj;
  int top[4] = {15, 15, 15, 15}; 
  for(int i = N; i >= 1; i--)
    top[getPos(i, _ring)] = i;
  
  for(int i = 0; i < 4; i++)
    for(int j = 0; j < 4; j++)
      if(i != j && top[j] > top[i]) 
        adj.push_back(setPos(_ring, top[i], j));
  return adj;
}
 
int sgn(int i)
{
    if(i == 0) return 0;
    return (i > 0 ? 1 : -1);
}
int minMove1(int start, int finish)
{
    if(start == finish) return 0;
 
    memset(d, 0, sizeof d);
 
    queue<int> q;
    q.push(start); q.push(finish);
    d[start] = 1; d[finish] = -1;
 
    while(true)
    {
        int here = q.front();
        q.pop();
        int count = d[here];
       
        vector<int> adjList = getAdjacent(here);
        for(int i = 0; i < adjList.size(); i++)
            if(d[adjList[i]] == 0)
            {
                q.push(adjList[i]);
                d[adjList[i]] = count + sgn(count);
            }
            else if(d[adjList[i]] * count < 0)
                return abs(d[adjList[i]]) + abs(count) - 1;     
    }
    return -1;
}
 
int main()
{
    
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int t;
    cin>>t;
    while(t--)
    {
        vector<vector<int> > input = vector<vector<int> >(4, vector<int>(0));
        cin>>N;
        for(int i = 0; i < 4; i++)
        {
            int vn;
            cin>>vn;
            while(vn--)
            {
                int tmp;
                cin>>tmp;
                input[i].push_back(tmp);
            }
        }
      
       cout<<minMove1(bitMask(input), (1<<(N*2)) - 1)<<"\n";
    }
    return 0;
}

 

 

 

 

 

 

 

 

HANOI4