[백준 10472번/JAVA] 십자뒤집기 (문제 풀이, 코드)

십자뒤집기

[문제]

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

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

 

[풀이]

처음에 3x3 흰 보드가 주어짐!

input으로 주어지는 보드로 최소 몇 번 만에 도달할 수 있는지?

보드(맵)이 있고, 최소 몇 번! 이면 이제 bfs나 dfs를 쓰자.

이문제는 한 방향으로 밀고가는 dfs보단 여러방향 한번에 넣는 bfs를 쓴다. 최소 몇번이니까.

 

[내 코드 알고리즘]

bfs를 하려면 방문 체크를 해야한다.

그런데 이 문제는 저 보드가 바뀌어서 방문체크를 어떻게 할지 잘 생각해봐야함.

나는 2진수<=>10진수 이 방식을 썼다. 

0은 흰색, 1은 검정색이다.

이런식으로 하면 모든 보드에 숫자를 부여해도 512개밖에 안나온다.

그래서 배열도 512개짜리로 만들어서 방문한 보드 번호를 체크하면 됨!

이때, 저거 보면 알겠지만 1번자리에 있는게 가장 마지막 이진수자리에 온다는거 명심!

따라서 1번자리가 자리수로 나타내면 8 정도 되겠다.

876

543

210

편의상 자릿수를 이제 저렇게 말하겠음!

8번자리를 클릭했을때 8,7,5가 흰백이 반전된다. 7번을 누르면 8764가 반전된다.

이 정보를 저장하는 배열을 하나 만들어서 반전시키는 걸 편하게 해두장

그리고 이제

000 000 000 인 상황에서 모든 자릿수를 클릭해보는 상황을 큐에 담고 하나씩 꺼내가면서 bfs를 하면 됨!

[코드]

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

class PC {
	int p;
	int c;
	PC(int p, int c){
		this.p = p;
		this.c = c;
	}
}

public class Main {
	static int ans;
	static boolean[] visited;
	static int[][] reverse = {{8,7,5},{8,7,6,4},{7,6,3},{8,5,4,2},{7,5,4,3,1},{6,4,3,0},{5,2,1},{4,2,1,0},{3,1,0}};
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int i=0; i<T; i++) {
			visited = new boolean[513];
			int p = 0;
			ans = 0;
			Queue<PC> next = new LinkedList<>();
			/* make ans */
			for(int j=0; j<3; j++) {
				String[] line = br.readLine().split("");
				for(int k=0; k<3; k++) {
					if(line[k].equals("*")) ans+= Math.pow(2, p+k);
				}
				p += 3;
			}
			
			/* bfs */
			next.add(new PC(0, 0));
			while(!next.isEmpty()) {
				PC pos = next.poll();
				if(visited[pos.p]) continue; 
				visited[pos.p] = true;
				if(pos.p == ans) {
					System.out.println(pos.c);
					break;
				}
				/* map에 이진수 변환해서 넣기! */
				String[] map = new String[9];
				String[] binaryPos = Integer.toBinaryString(pos.p).split("");
				for(int j=0; j<9; j++) map[j] = "0";
				int k = 8;
				for(int j=binaryPos.length-1; j>=0; j--) map[k--] = binaryPos[j];
				
				/* 클릭 후 방문안한 곳 넣기! */
				for(int j=0; j<9; j++) {
					String[] nextMap = map.clone();
					for(k=0; k<reverse[j].length; k++) {
						if(nextMap[reverse[j][k]].equals("0")) nextMap[reverse[j][k]] = "1";
						else nextMap[reverse[j][k]] = "0";
					}
					int nextPos = Integer.parseInt(String.join("",nextMap),2);
					if(!visited[nextPos]) next.add(new PC(nextPos, pos.c+1));
				}
			}
		}
	}
}

[어려웠던 점]

방문체크를 하기 위해 모든 보드에 번호를 줘야한다는 것을 생각하기 어려웠음.

번호를 어떻게 줄지 생각하는 것 역시 어려워씀.

왜 실버2밖에 안되지 ㅠㅠ

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.