[ BOJ ][JAVA][9079] 동전 게임

www.acmicpc.net/problem/9079

9079번: 동전 게임

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	171	123	106	72.603%

문제

상우는 재미있는 게임을 생각해냈다. 동전 9개를 아래 그림과 같이 3행 3열로 놓는다. H는 앞면, T는 뒷면을 의미한다.

H T T
H T T
T H H

게임의 목적은 이 동전의 모양을 모두 같은 면(H나 T)이 보이도록 하는 것이다. 단, 하나의 동전만을 뒤집을 수는 없고, 한 행의 모든 동전, 한 열의 모든 동전 또는 하나의 대각선 상의 모든 동전을 한 번에 뒤집어야 한다. 그런 식으로 세 개의 동전을 뒤집는 것을 '한 번의 연산'으로 센다. 상우는 이것을 최소 횟수의 연산으로 실행하고 싶어한다. 오랜 시간 생각한 끝에 위의 경우는 두 번의 연산으로 가능하다는 것을 알아냈고, 또, 이것이 최소인 것도 알아내었다.

H T T   T T T   T T T
H T T → T T T → T T T
T H H   H H H   T T T

또한, 모두 같은 면으로 만드는 것이 불가능한 모양이 있다는 것도 알아내었다. 다음이 그 예이다.

T H H
H H H
H H H

상우를 도울 수 있는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 주어진다.

출력

각 테스트 케이스에 대해서, 모두 같은 면이 보이도록 만들기 위한 최소 연산 횟수를 출력하고, 불가능한 경우에는 -1을 출력한다.

예제 입력 1

3
H T T
H T T
T H H
T H H
H H H
H H H
H H H
H T H
H H H

예제 출력 1

2
-1
4

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class p9079 {
    static int[] next;
    static boolean[] visited;
    static final int END = 511;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            next = new int[8];
            visited = new boolean[512];
            int start = 0;
            for (int i = 0; i < 3; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 3; j++) {
                    start *= 2;
                    if (st.nextToken().equals("H")) start++;
                }
            }
            visited[start] = true;
            Queue<Integer> q = new LinkedList();
            q.add(start);
            int result = 0;
            boolean finish = false;
            while (!q.isEmpty()) {
                Queue<Integer> temp = new LinkedList();
                while (!q.isEmpty()) {
                    temp.add(q.poll());
                }
                while (!temp.isEmpty()) {
                    int cur = temp.peek();
                    if (cur == END || cur == 0) {
                        finish = true;
                        break;
                    }
                    temp.poll();
                    find_next(cur);
                    for (int i = 0; i < 8; i++) {
                        if (!visited[next[i]]) {
                            visited[next[i]] = true;
                            q.add(next[i]);
                        }
                    }
                }
                if (finish) break;
                result++;
            }
            if (!finish) result = -1;
            System.out.println(result);
        }
    }

    static void find_next(int start) {
        next[0] = change(start, 0, 1, 2);
        next[1] = change(start, 3, 4, 5);
        next[2] = change(start, 6, 7, 8);
        next[3] = change(start, 0, 3, 6);
        next[4] = change(start, 1, 4, 7);
        next[5] = change(start, 2, 5, 8);
        next[6] = change(start, 0, 4, 8);
        next[7] = change(start, 2, 4, 6);
    }

    static int change(int val, int idx1, int idx2, int idx3) {
        val = val^(1<<idx1);
        val = val^(1<<idx2);
        val = val^(1<<idx3);
        return val;
    }

}