BOJ_1080_행렬

문제유형

그리디

문제풀이

Map의 좌표를 순회합니다. 그리고 before_map 과 after_map의 한점씩을 비교합니다. 서로 다를 경우에만 뒤짚는 연산을 수행합니다.
이 문제를 그리디로 해결하지 않고 연산을 뒤짚는 경우를 고려해본다면 (N-2) * (M-2) 이 연산의 개수가 됩니다. 즉, 연산을 하는 경우 그리고 연산을 하지 않는 경우가 생기니까 2^NM 즉, 2의 2500승이 됩니다. (N과 M은 50보다 작거나 같은 자연수입니다.) 

코드

package backjun;

import java.util.*;
import java.io.*;
public class BOJ_1080_행렬 {

	static int row;
	static int column;
	static char[][] row_map;
	static char[][] aim_map;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		row = Integer.parseInt(st.nextToken());
		column = Integer.parseInt(st.nextToken());
		
		row_map = new char[row][column];
		for(int i=0; i<row; i++) {
			row_map[i] = br.readLine().toCharArray();
		}
		
		aim_map = new char[row][column];
		for(int i=0; i<row; i++) {
			aim_map[i] = br.readLine().toCharArray(); 
		}
		
		System.out.println(DFS(0, row_map, aim_map, 0));
		//System.out.println(n);
	}
	static int DFS(int r, char[][] row_map, char[][] aim_map, int count) {
		boolean find = false;
		if(r>row*column-1) return -1;
		int rrow = r/column;
		int ccolumn = r%column;
		for(int i=0; i<row_map.length; i++) {
			for(int j=0; j<row_map[i].length; j++) {
				if(row_map[i][j] != aim_map[i][j])
					find = true;
			}
		}//end of for loop
		if(!find) {
			return count;
		}
		
		if(row_map[rrow][ccolumn]!=aim_map[rrow][ccolumn]) {
			if(rrow+2>=row || ccolumn+2>=column) 
				 return -1;
			for(int i=rrow; i<=rrow+2; i++) {
				for(int j=ccolumn; j<=ccolumn+2; j++) {
					if(row_map[i][j] == '1')
						row_map[i][j] = '0';
					else
						row_map[i][j] = '1';
				}
			}//end of for loop
			return DFS(r+1, row_map, aim_map, count+1);
		}else
		return DFS(r+1, row_map, aim_map, count);
		
	}

}