[Java] 백준 10472번 : 십자뒤집기

문제

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

10472번: 십자뒤집기

 

 

풀이 과정

데이터는 3x3으로 총 9개의 수가 주어지므로, int하나로 비트마스킹을 사용했다. 특정 상태까지의 최단 시간을 구하는 문제이므로 BFS를 사용했고 검은색은 1, 흰색은 0으로 비트마스킹해서 전체 값이 0이면 모두 흰색이므로 종료하도록 했다.

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(T-- > 0){
            int board = 0;
            for(int i=0; i<3; i++){
                String input = br.readLine();
                for(int j=0; j<3; j++){
                    if(input.charAt(j) == '*'){
                        int idx = i*3 + j;
                        board |= (1<<idx);
                    }
                }
            }
            sb.append(bfs(board)).append("\n");

        }
        System.out.println(sb);
    }

    public static int bfs(int start){
        int step = 0;
        int[] dx = {0, -1, 0, 1, 0}, dy = {0, 0, 1, 0, -1};
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[1<<9];
        visited[start] = true;
        q.add(start);

        outloop : while(!q.isEmpty()){
            int size = q.size();
            while(size-- > 0){
                int now = q.poll();
                if(now == 0){
                    break outloop;
                }

                for(int i=0; i<3; i++){
                    for(int j=0; j<3; j++){
                        int next = now;
                        for(int k=0; k<5; k++){
                            int nx = i + dx[k];
                            int ny = j + dy[k];
                            if(nx<0 || nx>=3 || ny<0 || ny>=3){continue;}
                            int pos = nx*3 + ny;
                            if((next & (1<<pos)) > 0){
                                next &= ~(1<<pos);
                            }
                            else{
                                next |= (1<<pos);
                            }
                        }
                        if(!visited[next]){
                            visited[next] = true;
                            q.add(next);
                        }
                    }
                }

            }
            step++;
        }

        return step;
    }
}

 

 

결과