9079

다익스트라를 이용해서 해결하면 간단하다. 여기서 오래 걸린거는 input값을 받는 것이다. scanf로 문자열을 받을때는 공백도 인식한다는 것에 주의해야하는데 그걸 알아채리지 못하고 쓸데 없이 시간을 많이 끌었다. 반성해야하는 부분이다...

 
#include<iostream>
#include<queue>
#include<cstdio>

using namespace std;

int d[(1<<9)];

const int MAX = 1<<9;

int allH = (1<<9)-1;
int allT = 0;

int edge[8][3] = {
	{ 0, 1, 2 },
	{ 3, 4, 5 },
	{ 6, 7, 8 },
	{ 0, 3, 6 },
	{ 1, 4, 7 },
	{ 2, 5, 8 },
	{ 0, 4, 8 },
	{ 2, 4, 6 }
};

int main(){
	int tc, res;
	char tmp;

	cin>>tc;

	while(tc--){
		int cur=0, up=1;
		res=-1;

		for(int i=0; i<9; i++){
			cin>>tmp;
			if(tmp=='H')
				cur+=up;
			up*=2;
		}

		for(int i=0; i<MAX; i++)
			d[i]=-1;

		priority_queue<pair<int, int> > pq;
		pq.push(make_pair(0, cur));

		while(!pq.empty()){
			pair<int, int> front=pq.top();
			pq.pop();
			int cur_d=-front.first;
			int cur_p=front.second;
			
			if(d[cur_p]!=-1 && d[cur_p] <= cur_d)
				continue;
			d[cur_p]=cur_d;

			if(cur_p == allH || cur_p == allT){
				res = cur_d;
				break;
			}

			for(int i=0; i<8; i++){
				int next_p = cur_p;
				for(int j=0; j<3; j++){
					if(cur_p & (1<<edge[i][j]))
						next_p -= 1<<edge[i][j];
					else
						next_p += 1<<edge[i][j];
				}
				pq.push(make_pair(-(cur_d+1), next_p));
			}
		}
		printf("%d\n", res);
	}
}