[백준] Q9079 동전게임 JAVA

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

9079번: 동전 게임

1. 문제의 유형 및 이해

완전탐색, bit연산

동전을 3행 3열로 놓을 때 앞면을 H 뒷면을 T라고 하자.

게임의 목적은 모든 동전을 같은 면으로 보이도록 하게하는 것이다.

한 번에 3개의 동전을 뒤집는 행위를 '한번의 연산'으로 셀 때 최소 횟수로 실행하고 싶다.

가로, 세로, 대각선 (항상 3개씩 뒤집어야함)

 

연산의 개수는 총 가로 3줄, 세로 3줄 대각선 2줄로 한번의 상태에서 총 8가지 상태로 뻗어나가게 됩니다.

동전이 9개로 놓여있을 때 나올 수 있는 가지는 총 $2^9$ 가지로 크지 않기 때문에 모든 경우를 확인할 수 있습니다.

2. 문제 접근 방법

동전의 상태

동전이 놓여져 있는 상태를 어떻게 표현할지에 대해서 고민하여야 합니다.

행렬을 이용하여 모든 경우를 확인하는 경우도 있을 수 있겠지만,

한 행을 기준으로 보았을 때 {{000}{001}...{111}}로 표현할 수 있기 때문에 한 행을 0~7로 상태를 표현해 줍니다.

 

한행을 0~7로 표현할 수 있을 때 전체 동전의 모양은 [8][8][8]의 상태 안에 있게 됩니다.

연산을 진행하면서 중복되는 상태가 되었을 때 방문여부를 isVisited[8][8][8]을 통해 확인 해 줄 수 있습니다.

 

연산을 해보자

뒤집어 주는 연산을 XOR 연산을 통하여 구현할 수 있습니다. 

우리가 저장하고 있는 값은 행의 값이기 때문에

1 0 0 (4)

1 0 0 (4)

0 1 1 (3) 와 같은 형태로 저장하고 있습니다.

행을 뒤집어 줄 때는 111과 XOR을 진행하여 해결할 수 있습니다.

열을 진행할 경우 1<<i 를 각 행에 XOR을 하게 되면 원하는 열을 뒤집을 수 있습니다.

이를 같이 적용하여 대각선의 경우 {4,2,1} 또는 {1,2,4}로 대각을 뒤집을 수 있습니다.

 

모든 경우에 대해 연산을 진행하면서 방문하지 않은 상태에 대해서만 확인하며 탐색을 진행합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @문제번호 : Q9079
 * @문제이름 : 동전게임
 * @난이도 : Silver IV
 * @date : 2022-03-24 오후 1:45
 * @author : pcrmcw0486
 * @문제이해
 * 동전을 모두 같은면이 보이도록 하고 싶다. (한 행의 모든 동전)(한열의 모든 동전)(하나의 대각선 모든 동전)
 * 최소 횟수의 연산으로 실행하고 싶다.
 * 모두 같은면으로 만드는 것이 불가능한 모양이 있다는 것도 알았다.
 * @알고리즘
 * 완전탐색
 * @접근방법

*/
public class Main {
    static class Table{
        int l1, l2, l3;

        public Table(int l1, int l2, int l3) {
            this.l1 = l1; this.l2 = l2; this.l3 = l3;
        }
    }

	//열 XOR 대각 XOR 
    static int[][] move = new int[][]{{4, 4, 4}, {2, 2, 2,}, {1, 1, 1,}, {4, 2, 1}, {1, 2, 4}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        while(T-- >0){
            int ans = -1;
            int[] data = new int[4];
            //상태 check 배열
            boolean[][][] isVisited = new boolean[8][8][8];
            for (int i = 0; i < 3; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 3; j++) {
                    if(st.nextToken().equals("H"))
                        data[i] |= 1<<(2-j);
                }
            }
            Queue<int[]> queue = new LinkedList<>();
            isVisited[data[0]][data[1]][data[2]] = true;
            queue.add(data);
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                int l1 = cur[0], l2= cur[1], l3 = cur[2];
                int d = cur[3];
                int nl1, nl2, nl3;
                if((l1==0&&l2==0&&l3==0) || (l1==7&&l2==7&&l3==7)){
                    ans = d;
                    break;
                }
                //행 뒤집기
                nl1 = l1^7;
                if(!isVisited[nl1][l2][l3]){
                    isVisited[nl1][l2][l3] = true;
                    queue.add(new int[]{nl1, l2, l3, d+1});
                }
                nl2 = l2^7;
                if(!isVisited[l1][nl2][l3]){
                    isVisited[l1][nl2][l3] = true;
                    queue.add(new int[]{l1, nl2, l3,d+1});
                }
                nl3 = l3^7;
                if(!isVisited[l1][l2][nl3]) {
                    isVisited[l1][l2][nl3]=true;
                    queue.add(new int[]{l1, l2, nl3,d+1});
                }
                //열 및 대각 뒤집기
                for (int i = 0; i < 5; i++) {
                    nl1 = l1^move[i][0];
                    nl2 = l2^move[i][1];
                    nl3 = l3^move[i][2];
                    if(!isVisited[nl1][nl2][nl3]){
                        isVisited[nl1][nl2][nl3] = true;
                        queue.add(new int[]{nl1, nl2, nl3, d + 1});
                    }
                }
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}