[BOJ] 14939. 불 끄기

import java.util.Scanner;

public class Main {
	static int N=10; // 전구가 배치된 정사각형의 한 변 길이
	static int cnt=0; // 맨 윗 줄 스위치 누른 횟수 
	static int ans=Integer.MAX_VALUE; // 정답을 저장할 변수 
	static int map[][]=new int[N][N]; // 전구 배치를 저장할 2차원 배열 
	static Scanner sc=new Scanner(System.in); // 입력을 위한 선언   
	
	public static void main(String[] args) {
		for (int i = 0; i < N; i++) { // 10회 반복 
			String s=sc.next(); // 한 줄 씩 입력 받음 
			for (int j = 0; j < N; j++) { // 입력받은 각 줄의 한 칸이 켜지면 1 꺼지면 0으로 map에 저장  
				if(s.charAt(j)=='O') {
					map[i][j]=1;
				}
				else { 
					map[i][j]=0;
				}
			}
			
		}
		
		go(0); // 2^10(1024)가지 경우의 수를 만들어 주기 위한 함수 실행.
		
		// ans 변수가 초기 선언 그대로이면 전구를 모두 끄는 것이 불가능하므로 -1 
		if(ans==Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(ans);
		}
	}
	
	// x번째 줄(세로) y번째 칸(가로)[ex. 좌측 최상단 0,0] 스위치를 눌렀을 때 전구 상태 반전을 위한 함수   
	public static void change(int x,int y,int map[][]) {
		// 제자리 반전(0은 1로 1은 0으로) 
		map[x][y]=map[x][y]^1;
		
		// 위 반전 
		if(x>0) map[x-1][y]=map[x-1][y]^1;

		// 아래 반전 
		if(x<N-1) map[x+1][y]=map[x+1][y]^1;
		
		// 왼쪽 반전 
		if(y>0) map[x][y-1]=map[x][y-1]^1;

		// 오른쪽 반전 
		if(y<N-1) map[x][y+1]=map[x][y+1]^1;
	}
	
	// 맨 윗 줄 전구 스위치 누르는 모든 2^10(1024)가지 경우의 수를 만들어 주기 위한 함수.
	public static void go(int d) {
		// 맨 윗 줄 스위치 누르는 모든 경우의 수 중에 하나가 만들어지면
		if(d==N) { 
			// map을 시뮬레이션 하기 위해 arr에 (깊은) 복사 한 뒤   
			int arr[][]=new int [N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j]=map[i][j];
				}
			}
			simulate(arr); // 맨 윗 줄 부터 켜져있는 칸을 끄기위해서 그 아래쪽 스위치를 누르도록 시뮬레이션 하는 함수 실행.
			return;
		}
		
		go(d+1); // 스위치 누르지 않고 다음 칸 스위치 누르는 상황으로 넘김

		change(0,d,map); // 0번째 줄(맨 윗 줄) d번째 칸 스위치 누른 다음   
		cnt++; // 맨 윗 줄 스위치 누른 횟수 한 번 증가시킴 
		go(d+1); // 스위치 누르고 다음 칸 스위치 누르는 상황으로 넘김
		change(0,d,map); // 끝났으면 0번째 줄(맨 윗 줄) d번째 칸 스위치 누르기 전 상태로 원상복귀(한 번 더 눌러줌으로써) 
		cnt--; // 맨 윗 줄 스위치 누른 횟수도 누르기 전 상태로 원상복귀 
	}
	
	// 맨 윗 줄 부터 켜져있는 칸을 끄기위해서 그 아래쪽 스위치를 누르도록 시뮬레이션 하는 함수.
	public static void simulate(int arr[][]) {
		int cnt2=0; // 맨 윗 줄 다음 줄 부터 스위치 누른 횟수 저장할 변수. 
		boolean lastRowFlag=true; // 마지막 줄 불 꺼져있는 지 확인할 변수. 
		
		// 맨 윗 줄 부터 켜져있는 칸을 끄기위해서 그 아래쪽 스위치를 누르도록 하는 반복문.
		for (int i = 1; i < N; i++) { // 맨 윗 줄 다음 줄 부터 마지막 줄 까지 한 줄 씩 
			for (int j = 0; j < N; j++) { // 맨 왼쪽에서 부터 한 칸 씩 검사  					
				if(arr[i-1][j]==1) { // 검사할 위치의 윗 칸 불이 켜져있으면  
					change(i,j,arr); // 검사할 위치의 스위치를 눌러준다.
					cnt2++; // 스위치 누른 횟수 증가.
				}
			}					
		}
		for (int j = 0; j < N; j++) { // 마지막 줄 불 꺼져있는지 확인하기 위한 반복문.
			if(arr[N-1][j]==1) { // 마지막 줄 맨 왼쪽부터 차례로 검사해서 켜져있으면 lastRowFlag를 false로 한 후 반복 종료 
				lastRowFlag=false;
				break;
			}
		}
		if(lastRowFlag) { // 마지막 줄의 불이 다 꺼져있다면.
			ans=Math.min(cnt+cnt2, ans); // 현재까지 최소로 모든 전구를 끄도록 스위치 누른 횟수와 비교하여 더 작은 값 ans에 저장.
		}
	}
}