백준 1455번) 뒤집기2 JAVA

https://www.acmicpc.net/problem/1455

1455번: 뒤집기 II

#문제 

세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다.

동전의 앞면을 0이라고 하고 뒷면을 1이라고 했을 때, 세준이는 모든 동전을 뒤집어서 앞면으로 만들려고 한다.

세준이가 (a,b)칸을 뒤집으려고 한다면, (i,j) (1 ≤ i ≤ a, 1 ≤ j ≤ b)의 조건을 만족하는 a×b개의 동전이 한번에 모두 뒤집힌다. (i는 위에서부터 위치의 위치이고, j는 왼쪽에서 부터의 위치이다.)

세준이가 뒤집어야하는 동전의 개수를 출력하시오. (a,b)칸을 선택해서 a×b개가 뒤집혔다면, 동전을 뒤집은 횟수는 a×b가 아니라 1이다.

 

#알고리즘

그리디

 

#난이도

silver2

 

#풀이방법

내가 제일 어려워하는 그리디문제이지만 난이도가 높지 않아서 많은 시간이 걸리지는 않았다.. 

풀이 방법은 간단했다. while문을 돌려 모든 동전들이 뒤집어질때까지 루프문을 돌리고

배열을 끝에서부터 탐색한후 동전 뒷면 즉 1이 있을 경우 해당되는 모든 동전들을 뒤집어준다.

이후 뒤집어주는 갯수를 ++한 후, continue를 이용해 다시 while문에 조건에 맞추어 반복시킨다.

 

#코드

import java.util.*;
//1t

public class Main {
	
	static char[][] coin;
	
	public static boolean complete() {
		
		for(int i=0; i<coin.length; i++) {
			for(int j=0; j<coin[0].length; j++) {
				if(coin[i][j] == '1')
					return false;//뒷면이 있을 경우 false 반환
			}
		}
		return true;
	}//모두다 앞면인지 확인해주는 메소드
	
	public static void flip_over(int i,int j){
		
		for(int k=0; k<i+1; k++) {
			for(int m=0; m<j+1; m++) {
				
				if(coin[k][m] == '0')
					coin[k][m] = '1';
				else
					coin[k][m] = '0';
			}
		}
		
	}//a,b까지 동전 뒤집어주기

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		coin = new char[N][M];
		
		int flip = 0;
	
		for(int i=0; i<N; i++) {
			String s = sc.next();
			
			for(int j=0; j<s.length(); j++) {
				coin[i][j] = s.charAt(j);
			}
		}
		
		while(!complete()) {
			
			for(int i=N-1; i>-1; i--) {
				for(int j=M-1; j>-1; j--) {
					
					if(coin[i][j] == '1') {
						flip_over(i,j);//해당위치를 뒤집어줌
						flip++;//뒤집기 갯수 +1
						continue;//다시 루프로 돌아가기
					}//뒷면일 경우
					
				}
			}//배열의 끝에서부터 탐색한다.
	
		}//모든 동전이 앞면일때까지 계속 진행됨
		
		System.out.println(flip);
		
		
	}

}