십자뒤집기

문제

십자뒤집기

문제 설명

당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색에서 흰색으로, 혹은 흰색에서 검은색으로 변할 것이다.

당신은 모든 칸이 흰색인 3x3 보드를 입력으로 주어지는 보드의 형태로 바꾸려고 한다. 보드를 회전시킬수는 없다.

Figure D.1: 예제 입력

제한 사항

첫 줄에는 테스트 케이스의 숫자 P(0 < P ≤ 50)이 주어진다.

각각의 테스트 케이스에 대해서 세 줄에 걸쳐 한 줄에 세 글자씩이 입력으로 들어온다. "*"은 검은색을 뜻하며 "."은 흰색을 뜻한다.

입출력 예

입력	출력

| 2
..
**.
..

---

..
.. | 1
3 |

아이디어

이동할 수 있는 것 하드코딩 후

큐에 넣을 때 현재의 맵, 방문 기록을 함께 넣음

크기가 3*3로 고정되어있어서 가능한 듯

3*3 → 9로 풀어서 배열로 사용

제출 코드

package com.example.javacodingtest.boj.gold;

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

public class five10472 {
    static HashMap<Integer, int[]> filps = new HashMap<>();
    static final char BLACK = '*';
    static int map[];
    static int[] isFliped;

    public void solution() throws IOException {
        init();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int testNum = Integer.parseInt(reader.readLine());
        for (int test = 0; test < testNum; test++) {
            // 입력부
            map = new int[10];
            isFliped = new int[10];
            for (int i = 0; i < 3; i++) {
                String input = reader.readLine();
                for (int j = 0; j < 3; j++) {
                    map[i * 3 + j] = (input.charAt(j) == BLACK) ? 1 : 0 ;
                }
            }
            System.out.println(bfs());
        }
    }

    private int bfs() {
        Deque<int[][]> toFlip = new ArrayDeque<>();
        toFlip.add(new int[][] {map, isFliped});

        while (!toFlip.isEmpty()) {
            int[][] current = toFlip.poll();

            if (isComplete(current[0])) {
                return current[0][9];
            }

            for (int i = 0; i < 9; i++) {
                if (current[1][i] == 1) continue; // 이미 뒤집었다면 패스

                int[] newMap = current[0].clone();
                int[] newIsFliped = current[1].clone();

                for (int flip : filps.get(i)) { // 뒤집기s
                    newMap[flip] = newMap[flip] == 0 ? 1 : 0;
                }

                newIsFliped[i] = 1;
                newMap[9]++;

                toFlip.add(new int[][] {newMap, newIsFliped});
            }
        }
        return 0;
    }

    private boolean isComplete(int[] map) {
        for (int i = 0; i < 9; i++) {
            if (map[i] == 1) return false;
        }
        return true;
    }

    private void init() {
        filps.put(0, new int[] {0, 1, 3});
        filps.put(1, new int[] {1, 0, 2, 4});
        filps.put(2, new int[] {2, 1, 5});
        filps.put(3, new int[] {3, 0, 4, 6});
        filps.put(4, new int[] {4, 1, 3, 5, 7});
        filps.put(5, new int[] {5, 2, 4, 8});
        filps.put(6, new int[] {6, 3, 7});
        filps.put(7, new int[] {7, 4, 6, 8});
        filps.put(8, new int[] {8, 5, 7});
    }

    public static void main(String[] args) throws IOException {
        new five10472().solution();
    }
}