[ baekjoon ] 뒤집기 II 1455번 (Java )

🎈 문제

백준 1455 뒤집기 II 풀이 ( 자바 )

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

1455번: 뒤집기 II

 

🎁 풀이

천천히 생각 해봤는데 어떤 점을 찍었을 때 왼쪽 맨 위의 점과 찍은 점으로 만들어 지는 사각형에만 영향을 줬다.

그래서

이 순서대로 가다가 1을 발견할때마다 뒤집으면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int answer = 0;
        arr = new int[n][m];

        for(int i = 0; i < n; i++) {
            String[] tmp = br.readLine().split("");
            for(int j = 0; j < m ; j++){
                arr[i][j] = Integer.parseInt(tmp[j]);
            }
        }

        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                if(arr[j][i] == 1) {
                    reverse(j, i);
                    
                    answer += 1;
                }
                
            }
        }

        System.out.println(answer);
    }

    static void reverse(int x, int y) {
        for(int i = 0; i <= x; i++) {
            for(int j = 0; j <= y; j++) {
                if(arr[i][j] == 1){
                    arr[i][j] = 0;
                }else{
                    arr[i][j] = 1;
                }
            }
        }
    }

    
}