동전 게임

동전 게임

풀이

최소 연산 횟수를 구해야 한다.
그렇기 때문에 bfs를 생각해야 한다.
조건에서 가능한 경우는 4가지가 있다. 한 행, 한 열, 대각선 \, 대각선 /
bfs를 사용하려면 방문처리를 해야한다.
이 때 비트마스킹이 사용된다.

HTT
HTT
THH
가 있을 때 비트마스크로 나타내면 011011100 => T가 1, H가 0이라 가정

비트마스크와 4가지 경로를 사용해서 탐색하다가 0이나 511이 나올 경우 종료한다.

비트를 1로 바꾸고 싶을 때에는 bitmask |= (1 << 위치)
비트를 0로 바꾸고 싶을 때에는 bitmask &= ~(1 << new_par)
해당 비트가 1인지 0인지 확인할 때에는 (bitmask & (1 << 위치)) == 0 여부를 판단하면 된다. 해당값이 0이면 0, 1이면 0이 아닌 값이 된다.

결과

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static char[][] graph = new char[3][3];
	static int ans = Integer.MAX_VALUE; 
	static boolean[] visited;
	public static void main(String[] args) throws IOException {		
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedReader br = new BufferedReader(new FileReader("./input.txt"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());

		for (int t = 0; t < N; t++) {
			for (int row = 0; row < 3; row++) {
				st = new StringTokenizer(br.readLine());
				visited = new boolean[512];
				
				for (int col = 0; col < 3; col++) {
					graph[row][col] = st.nextToken().charAt(0);
				}
			}
			bfs(getBit());
		}
		
//		System.out.println(13 & ~(1 << 2));
	}
	
	static void bfs(int bit) {
		Deque<int[]> deque = new LinkedList<>();
		boolean flg = false;
		deque.add(new int[] {bit, 0});
		visited[bit] = true;
		
		while (!deque.isEmpty()) {
			int[] cur_arr = deque.pollFirst();
			int cur_bit = cur_arr[0];
			int cur_cnt = cur_arr[1];
			
			if (cur_bit == 0 || cur_bit == 511) {
				System.out.println(cur_cnt);
				flg = true;
				break;
			}

			for (int new_bit : reverse_row(cur_bit))
				deque.add(new int[] {new_bit, cur_cnt + 1});
			
			
			for (int new_bit : reverse_col(cur_bit)) 
				deque.add(new int[] {new_bit, cur_cnt + 1});

			
			for (int new_bit : reverse_cross_1(cur_bit)) 
				deque.add(new int[] {new_bit, cur_cnt + 1});
			
			
			for (int new_bit : reverse_cross_2(cur_bit)) 
				deque.add(new int[] {new_bit, cur_cnt + 1});
			
		}
		if (!flg) System.out.println(-1);
	}
	
	static ArrayList<Integer> reverse_row(int cur_bit) {
		// row
		ArrayList<Integer> list = new ArrayList<>(); 
		int[] par = new int[] {8, 7, 6}; 
		for (int col = 0; col < 3; col++) {
			int new_bit = cur_bit;
			int new_par = par[col];
					
			for (int row = 0; row < 3; row++) {
				if ((cur_bit & (1 << new_par)) == 0) new_bit |= (1 << new_par);
				else new_bit &= ~(1 << new_par);
				
				new_par -= 3;
			}

			if (visited[new_bit]) continue;
			visited[new_bit] = true;
			list.add(new_bit);
		}
		
		return list;
	}
	
	static ArrayList<Integer> reverse_cross_1(int cur_bit) {
		ArrayList<Integer> list = new ArrayList<>(); 
		int[] par = new int[] {8, 4, 0};
		int new_bit = cur_bit;
		
		for (int row = 0; row < 3; row++) {
			int new_par = par[row];
			if ((cur_bit & (1 << new_par)) == 0) new_bit |= (1 << new_par);
			else new_bit &= ~(1 << new_par);
		}
		if (visited[new_bit]) return list;
		else {
			visited[new_bit] = true;
			list.add(new_bit);
			return list;
		}
	}
	
	static ArrayList<Integer> reverse_cross_2(int cur_bit) {
		ArrayList<Integer> list = new ArrayList<>(); 
		int new_bit = cur_bit;

		if ((cur_bit & (1 << 6)) == 0) new_bit |= (1 << 6);
		else new_bit &= ~(1 << 6);
		
		if ((cur_bit & (1 << 4)) == 0) new_bit |= (1 << 4);
		else new_bit &= ~(1 << 4);
		
		if ((cur_bit & (1 << 2)) == 0) new_bit |= (1 << 2);
		else new_bit &= ~(1 << 2);
		
		if (visited[new_bit]) return list;
		else {
			visited[new_bit] = true;
			list.add(new_bit);
			return list;
		}
	}
	
	static ArrayList<Integer> reverse_col(int cur_bit) {
		// col
		ArrayList<Integer> list = new ArrayList<>(); 
		int[] par = new int[] {8, 5, 2}; 
		for (int row = 0; row < 3; row++) {
			int new_bit = cur_bit;
			int new_par = par[row];
					
			for (int col = 0; col < 3; col++) {
				if ((cur_bit & (1 << new_par)) == 0) new_bit |= (1 << new_par);
				else new_bit &= ~(1 << new_par);
				
				new_par--;
			}
			
			if (visited[new_bit]) continue;
			visited[new_bit] = true;
			list.add(new_bit);
		}
		
		return list;
	}
	
	static int getBit() {
		//HTT HTT THH  T => 1
		int par = 8;
		int bitmask = 0;
		
		for (int row = 0; row < 3; row++) {
			for (int col = 0; col < 3; col++) {
				if (graph[row][col] == 'T') bitmask += Math.pow(2, par);
				par--;
			}
		}
		
		return bitmask;
	}
}