[백준 9079번] 동전 게임 -JAVA

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

9079번: 동전 게임

풀이

사용한 알고리즘 : 비트마스크, bfs

 

풀이전략

1. 주어지는 3x3 행렬을 2진수 숫자 하나로 변환한다.

  ex) H=1, T=0이라고 할 때,

     HTT

     HTT   =   100100011(2)

     THH

2. 행을 하나 뒤집었을 경우, 열을 하나 뒤집었을 경우, 대각선으로 뒤집었을 경우 등  가능한 모든 경우를

   탐색하기 위해 BFS를 사용한다. 이 때, 연산을 수행할 때마다 count를 1 증가시킨다.

3. BFS 탐색 중 모든 비트가 0(=0)이거나 모두 1(=511)인 경우, 연산 수행 횟수인 count를 출력한다.

 

제출코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    static class Node{
        int num;
        int count;

        public Node(int num,int count){
            this.num=num;
            this.count=count;
        }
    }

    static int bfs(int start){
        Queue<Node> q = new LinkedList<>();
        boolean visited[]=new boolean[512];
        visited[start]=true;

        Node node=new Node(start,0);

        q.offer(node);
        while(!q.isEmpty()){
            Node x = q.poll();

            if(x.num==0 || x.num==511){
                return x.count;
            }
            
            //행 뒤집기
            for(int i=0;i<3;i++){
                Node y=new Node(x.num,x.count);
                y.num^=(448>>(3*i));
                if(!visited[y.num]){
                    visited[y.num]=true;
                    Node temp = new Node(y.num,y.count+1);
                    q.offer(temp);
                }
            }

            //열 뒤집기
            for(int i=0;i<3;++i){
                Node y=new Node(x.num,x.count);
                y.num^=(292>>1*i);
                if(!visited[y.num]){
                    visited[y.num]=true;
                    Node temp = new Node(y.num,y.count+1);
                    q.offer(temp);
                }
            }

            //대각선(\) 256+16+1
            Node y=new Node(x.num,x.count);
            y.num^=273;
            if(!visited[y.num]){
                visited[y.num]=true;
                Node temp = new Node(y.num,y.count+1);
                q.offer(temp);
            }

            //대각선(/) 64+16+4
            y=new Node(x.num,x.count);
            y.num^=84;
            if(!visited[y.num]){
                visited[y.num]=true;
                Node temp = new Node(y.num,y.count+1);
                q.offer(temp);
            }
        }
        return -1;
    }

    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        StringTokenizer st;
        int T = Integer.parseInt(scanner.nextLine());

        while(T!=0){
            int num=0;
            for(int i=0;i<3;++i){
                st=new StringTokenizer(scanner.nextLine());
                for(int j=0;j<3;++j){
                    int val=0;
                    num=num<<1;
                    if(st.nextToken().equals("H")){
                        val=1;
                        num+=1;
                    }
                }
            }
            System.out.println(bfs(num));
            --T;
        }
    }
}