백준 1080 - 행렬
문제
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)
입력
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다
Test Case
Input
3 4
0000
0010
0000
1001
1011
1001output
2
풀이
처음엔 굉장히 까다롭다고 생각했다. 어느 위치를 기준으로 3x3 크기의 원소들을 뒤집으면, 다음 뒤집을 때 영향을 준다고 생각했기 때문이다. 최소한의 횟수를 구해야하기 때문이다.
최소로 뒤집는 케이스에 대해서 어떤 원소는 1번, 혹은 3번, 4번 뒤집힐 수도 있다는 말이다.
문제를 다시 살펴보면, 사실 어떤 원소가 얼마나 뒤집혔는지는 중요하지 않다. 결과적으로 행렬 A와 B가 동일해지는게 중요하다.
3x3 행렬을 뒤집을 때, (x, y)를 기준으로
(x, y), (x + 1, y), (x + 2, y)
(x, y + 1), (x + 1, y + 1), (x + 2, y + 1)
(x, y + 2), (x + 1, y + 2), (x + 2, y + 2)
의 영역이 뒤집힌다는 점을 주목해보자.
만약 [행렬A] (x + 1, y + 1)의 원소가 행렬B와 다른 경우는
(x + 1, y) 혹은 (x, y + 1)에서 뒤집히는 연산이 이루어지면 바뀔 수 있지만
(x, y)의 원소가 [행렬B]와 다르다면 무조건 이 위치에서, 최소 횟수 조건과 상관없이 뒤집혀야 한다.
이 아이디어를 차용하여, 행렬A를 모두 순회하면서 해당 위치의 원소가 행렬B와 다른 경우 뒤집는 연산을 하면 정답을 구할 수 있다.
구현 코드
- 뒤집는 연산
//행렬A를 순회 (x,y)를 기준으로 +2, +2까지 뒤집으므로,
// N - 2, M - 2까지만 탐색
for (int i = 0; i < N - 2; i++) {
for (int j = 0; j < M - 2; j++) {
if (matA[i][j] != matB[i][j]) {
changeSquareBoard(i, j);
answer++;
}
}
}
private static void changeSquareBoard(int startY, int startX) {
for (int i = startY; i < startY + 3; i++) { //3x3만큼만 뒤집기
for (int j = startX; j < startX + 3; j++) {
if (matA[i][j] == 1) {
matA[i][j] = 0;
} else {
matA[i][j] = 1;
}
}
}
}
- 예외
N 혹은 M이 3보다 작으면, 뒤집는 연산을 수행 할 수 없다
if (N < 3 || M < 3) {
if (isSameMatrix(N, M)) {
System.out.println("0");
} else {
System.out.println("-1");
}
return;
}- 두 행렬 비교
private static boolean isSameMatrix(int N, int M) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matA[i][j] != matB[i][j]) {
return false;
}
}
}
return true;
}정답 코드
public class Boj_1080 {
private static int[][] matA;
private static int[][] matB;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String NM = br.readLine();
int N = Integer.parseInt(NM.split(" ")[0]);
int M = Integer.parseInt(NM.split(" ")[1]);
matA = new int[N][M];
matB = new int[N][M];
//MatA 입력
for (int i = 0; i < N; i++) {
String row = br.readLine();
for (int j = 0; j < M; j++) {
matA[i][j] = Integer.parseInt(String.valueOf(row.charAt(j)));
}
}
//MatB 입력
for (int i = 0; i < N; i++) {
String row = br.readLine();
for (int j = 0; j < M; j++) {
matB[i][j] = Integer.parseInt(String.valueOf(row.charAt(j)));
}
}
if (N < 3 || M < 3) {
if (isSameMatrix(N, M)) {
System.out.println("0");
} else {
System.out.println("-1");
}
return;
}
int answer = 0;
for (int i = 0; i < N - 2; i++) {
for (int j = 0; j < M - 2; j++) {
if (matA[i][j] != matB[i][j]) {
changeSquareBoard(i, j);
answer++;
}
}
}
if (!isSameMatrix(N, M)) {
answer = -1;
}
System.out.println(answer);
}
private static boolean isSameMatrix(int N, int M) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matA[i][j] != matB[i][j]) {
return false;
}
}
}
return true;
}
private static void changeSquareBoard(int startY, int startX) {
for (int i = startY; i < startY + 3; i++) {
for (int j = startX; j < startX + 3; j++) {
if (matA[i][j] == 1) {
matA[i][j] = 0;
} else {
matA[i][j] = 1;
}
}
}
}
}굉장히 직관적인 풀이다.
성능은
