알고리즘
보호필름 설계 & 구현
리키타카
2019. 9. 24. 16:46
링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | package swexpertmoitest; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class 보호필름 { public static boolean flag = false; public static int n; public static int t, d, w, k; public static int[][] map, backup; public static int[] filmJohab; public static ArrayList<Integer> arrList = new ArrayList(); public static void main(String[] args) { Scanner scan = new Scanner(System.in); t = scan.nextInt(); for (int i = 1; i <= t; i++) { input(scan); for (int j = 0; j <= k; j++) { n = j; function1(0, 0, i); } flag = false; } scan.close(); } private static void function1(int depth, int y, int i) { if (flag) return; if (depth == n) { // System.out.println("어디 둘래:"+arrList.toString()); filmJohab = new int[arrList.size()]; makeFilmJohab(0, i); if (flag) return; return; } else if (y == d) { return; } arrList.add(y); function1(depth + 1, y + 1, i); int len = arrList.size(); arrList.remove(len - 1); function1(depth, y + 1, i); } private static void recoverMap2() { for (int i = 0; i < d; i++) { for (int j = 0; j < w; j++) { map[i][j] = backup[i][j]; } } } private static void changeMap() { // 어디에 둘 지 // 어떻게 둘 지 for (int i = 0; i < arrList.size(); i++) { int row = arrList.get(i); int val = filmJohab[i]; for (int k = 0; k < w; k++) { map[row][k] = val; } } } private static boolean checkMap() { for (int i = 0; i < w; i++) { int curVal = map[0][i]; int cnt = 1; for (int j = 1; j < d; j++) { if (map[j][i] == curVal) { cnt += 1; } else { cnt = 1; curVal = map[j][i]; } if (cnt == k) break; } if (cnt < k) return false; } return true; } private static void makeFilmJohab(int depth, int idx) { if (flag) return; if (depth == n) { // System.out.println("어떻게 둘래?->"+Arrays.toString(filmJohab)); changeMap(); if (checkMap()) { flag = true; } recoverMap2(); if (flag) { System.out.println("#" + idx + " " + depth); recoverMap2(); return; } return; } filmJohab[depth] = 0; makeFilmJohab(depth + 1, idx); filmJohab[depth] = 1; makeFilmJohab(depth + 1, idx); } private static void input(Scanner scan) { d = scan.nextInt(); w = scan.nextInt(); k = scan.nextInt(); map = new int[d][w]; backup = new int[d][w]; for (int i = 0; i < d; i++) { for (int j = 0; j < w; j++) { map[i][j] = scan.nextInt(); backup[i][j] = map[i][j]; } } } private static void printMap() { for (int i = 0; i < d; i++) { for (int j = 0; j < w; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } } } | cs |
2회차 소스 (1:57 ~ 2:43) 약 45분 (설계/구현 포함)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
public static boolean flag = false;
public static ArrayList<Integer> arrList = new ArrayList<Integer>();
public static int t, d, w, k;
public static int[][] map, backup;
public static int limit;
public static int[] color;
public static int ans = 0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
t = scan.nextInt();
for (int i = 1; i <= t; i++) {
input(scan);
protectFilm();
System.out.println("#" + i + " " + ans);
flag = false;
ans = 0;
}
scan.close();
}
private static void protectFilm() {
for (int i = 0; i <= d; i++) {
limit = i;
johab(0, 0);
if (flag)
return;
}
}
private static void johab(int depth, int y) {
if (flag)
return;
if (arrList.size() == limit) {
// System.out.println(arrList.toString());
color = new int[limit];
// 어떻게 넣을건데
tobin(0);
if (flag) {
return;
}
return;
} else if (y >= d) {
return;
}
arrList.add(y);
johab(depth + 1, y + 1);
int len = arrList.size() - 1;
arrList.remove(len);
johab(depth, y + 1);
}
private static void tobin(int depth) {
if (depth == limit) {
// System.out.println("color:"+Arrays.toString(color));
/* 지도수정 */
modifyMap();
// 확인하기
if (check()) {
ans = depth;
flag = true;
}
// 지도 복구
recoverMap();
return;
}
color[depth] = 1;
tobin(depth + 1);
color[depth] = 0;
tobin(depth + 1);
}
private static boolean check() {
for (int i = 0; i < w; i++) {
int std = map[0][i];
int cnt = 1;
for (int j = 1; j < d; j++) {
if (map[j][i] == std) {
cnt += 1;
} else {
std = map[j][i];
cnt = 1;
}
if (cnt == k)
break;
}
if (cnt < k)
return false;
}
return true;
}
private static void recoverMap() {
for (int i = 0; i < d; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = backup[i][j];
}
}
}
private static void modifyMap() {
for (int i = 0; i < arrList.size(); i++) {
int temp = arrList.get(i);// 열
int col = color[i];// 색
for (int j = 0; j < w; j++) {
map[temp][j] = col;
}
}
}
private static void printmap() {
for (int i = 0; i < d; i++) {
for (int j = 0; j < w; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
private static void input(Scanner scan) {
d = scan.nextInt();
w = scan.nextInt();
k = scan.nextInt();
map = new int[d][w];
backup = new int[d][w];
for (int j = 0; j < d; j++) {
for (int k = 0; k < w; k++) {
map[j][k] = scan.nextInt();
backup[j][k] = map[j][k];
}
}
}
}
//1 2 0 0
|
cs |