2018. 8. 6. 00:26ㆍAlgorithm
문제
0과 1로만 이루어진 행렬 A, B가 존재한다.
3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 연산을 이용해 A -> B로 변환하는데 필요한 최소 횟수는?
해결
알고리즘
그리디 알고리즘을 사용해 해결하였다.
값이 변경된 부분을 기준으로 뒤집어 간 후 남은 부분은 동일 여부에 따라 판단하면 된다고 가정하였고, 그 증명이 가능했기 때문.
그리디 알고리즘에 대해 잘 모르신다면 이 글을 참고하세요!
방법
1. A와 B 비교 값을 저장한 check 배열
A와 B의 각 위치를 비교하면 다음과 같은 결론을 낼 수 있다.
- 값이 같다.
: 연산을 거치지 않았거나 짝수 번의 연산을 거쳐 값이 돌아옴. - 값이 다르다.
: 연산을 홀수 번 거쳐 값이 변경됨.
이를 활용해서 값이 달라진 곳만 true로 저장해둔 2차원 배열 check를 생성하였다.
우리는 이 check 배열만을 활용해 문제를 풀 수 있다.
true는 값이 변한 곳을 나타낸다. 변한 곳 들을 연산을 적용해 다시 뒤집어준다면 원상복귀 될터.
원상복귀 하는 최소의 연산 횟수 = 우리가 찾는 A->B를 위한 연산의 최소 횟수
즉, True들을 False로 만드는게 우리의 목표가 되었다!
2. 3*3 연산의 기준, 수행 범위는?
우리는 Check 배열의 각 위치 = 3*3 배열의 (0, 0)라 생각하고 연산을 진행할 것이다.
때문에 우리는 Check배열의 (0, 0) ~ (n - 3, m - 3)의 범위만 확인하면 된다.
3. 횟수를 구하자.
2에 맞춰 Check 배열을 확인 후 true일 경우 뒤집는 연산을 해주면 된다.
연산과정을 거칠 때 마다 횟수를 세어주자. 최종 연산 횟수가 찾고자 하는 최소 값이다.
하지만, 우리는 불가능한 케이스도 찾아야 한다.
불가능한 케이스를 어떻게 찾을 수 있을까?
4. 예외처리 1 : 핵심은 끝이다.
우리는 2번에서 Check배열의 (0, 0) ~ (n - 3, m - 3)의 범위만 확인하면 된다는 사실을 알았다.
확인하지 않는 위치의 값들을 통해 우리는 A -> B변환 가능여부를 알 수 있다.
왜?
예시를 통해 확인하자.
위의 예시에서 x = 0, y = m - 3일 때 색칠 된 부분에 영향이 간다.
회색 부분이야 아래 행으로 넘어가면 변할지도 모르는 값들이기 때문에 상관 없지만, 보라색 부분은 y = m - 3 이후로 값이 변하지 않는다.
그런데 이 보라색 부분의 값이 서로 다르다면 T -> F로 모두 바꾸지 못할 것이다.
따라서, 3번 과정에서 x = n - 3, y = m - 3일 경우 마지막 3개의 값이 모두 동일하지 않다면 모두 멈추고 -1을 출력한다.
마찬가지로 모든 위치를 확인 한 후에 오른쪽 하단 2*2 위치와 (n - 3, m - 3)위치의 값들이 모두 동일한지도 확인해야 할 것이다.
4. 예외처리 2 : 3*3보다 작은 input
여담이지만, 이 부분을 고려하지 못해서 계속 틀렸었다.
3*3보다 작은 크기는 연산 자체가 불가하다.
따라서 A와 B의 모든 값이 같으면 답이 0일 것이고, 다르다면 -1일 것이다.
.
구현 java
조금 더 시간을 줄이기 위하여, 금액보다 큰 동전은 배제하였다.
1.import java.util.*;
2.
3.public class Main {
4. public static void main(String[] args) {
5. Scanner sc = new Scanner(System.in);
6. int n = sc.nextInt();
7. int m = sc.nextInt();
8. char[][] A = new char[n][m];
9. boolean[][] check = new boolean[n][m]; // 짝수 : false, 홀수 : true
10.
11. // A배열 인풋
12. for (int i = 0; i < n; i++)
13. A[i] = sc.next().toCharArray();
14. // B배열 인풋 받으면서 동시에 A와 비교
15. // 동일할 경우 : 짝수번 뒤집힘, 다를 경우 : 홀수번 뒤집힘
16.
17. int diff = 0;
18. for (int i = 0; i < n; i++) {
19. char[] inputs = sc.next().toCharArray();
20. for (int j = 0; j < m; j++) {
21. if (inputs[j] != A[i][j]) {
22. check[i][j] = true;
23. diff++;
24. }
25. }
26. }
27.
28. if (diff == 0)
29. System.out.println(0);
30. else
31. System.out.println(getAnswer(check));
32. }
33.
34. static int getAnswer (boolean[][] check) {
35. int n = check.length;
36. int m = check[0].length;
37.
38. if (n < 3 || m < 3)
39. return -1;
40.
41. int count = 0;
42. for (int i = 0; i <= n - 3; i++) {
43. for (int j = 0; j <= m - 3; j++) {
44. // 마지막 3개가 다 다를 경우 불가능하다.
45. if (i == n - 3 && !(check[i][j] == check[i + 1][j] && check[i][j] == check[i + 2][j]))
46. return -1;
47. if (j == m - 3 && !(check[i][j] == check[i][j + 1] && check[i][j] == check[i][j + 2]))
48. return -1;
49. // 가능한 경우 홀수 일때 3x3을 모두 뒤집는다.
50. if (check[i][j]) {
51. reverse(check, i, j);
52. count++;
53. }
54. }
55. }
56. boolean flag = check[n - 3][m - 3];
57. for (int i = n - 1; i > n - 3; i--) {
58. for (int j = m - 1; j > m - 3; j--) {
59. if (flag != check[i][j]) return -1;
60. }
61. }
62. return count;
63. }
64.
65. static void reverse (boolean[][] check, int x, int y) {
66. for (int i = x; i < x + 3; i++) {
67. for (int j = y; j < y + 3; j++)
68. check[i][j] = !check[i][j];
69. }
70. }
71.}
결과
