https://www.acmicpc.net/problem/17106
17106번: 빙고
한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과
www.acmicpc.net
풀이
1) 직접 경우를 따져가며 문제를 푸는 방법, 2) 가지수가 2^25 밖에(?) 안 되니 브루트포스 코드를 작성하여 푼 후 제출하는 방법이 있습니다. 저는 2번으로 문제를 풀었습니다. 2번 풀이가 어떻게 보면 '머리가 나빠서 몸이 고생하는' 풀이처럼 보이지만, 관점을 바꾸어 1번 풀이가 '몸이 나빠서 머리가 고생하는' 풀이라고 생각합시다. 참고로, 1번 풀이는 에디토리얼이 있습니다.
25개 칸마다 참/거짓일 수 있으므로 총 2^25가지 경우가 있습니다. 각 경우마다, 첫 번째 칸 부터 맨 마지막 칸까지 참거짓 배치가 가능한지 판단해야 합니다. 빙고 칸 내의 문장이 참이면 해당 칸도 참, 반대로 문장이 거짓이면 해당 칸도 거짓이여야 하므로, 만약 (문장의 참거짓) ^ (해당 칸의 참거짓)이 참이라면 두 명제의 참거짓이 반대라는 뜻이므로 성립하지 않습니다.
구현이 조금 번거로우나, 시간 복잡도를 - 컴퓨터가 적당한 시간 내에 풀어낼 수만 있는 수준 내에서 - 전혀 생각하지 않아도 되기에 직관적으로 구현하여 풀면 됩니다.
다만, B5 칸 조건이 되게 메타적인데, B5를 제외하고 나머지 조건을 확인하여 코드를 실행하면 두 가지 경우가 나옵니다.
.#..#
#####
..#.#
.##.#
##.##
.#..#
#####
..#.#
.##.#
#..##
즉, B5 칸이 참인 경우, 거짓인 경우 2가지가 있습니다. 이제 B5 칸의 문장의 참거짓을 판단해봅시다.
만약 B5 칸의 문장이 참이라면, B5 칸이 거짓인 경우는 정답이 될 수 없으니 정답은 1개입니다. 이렇게 되면 문장이 거짓이 되므로, 모순입니다. 따라서, B5 칸의 문장은 거짓이며, 후자만 정답이 됩니다.
코드 구현
|
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
|
import java.io.*;
import java.util.*;
public class Main {
static boolean[][] bingo = new boolean[5][5];
public static void main(String[] args) {
solve(0);
}
static void solve(int cnt) {
if (cnt == 25) {
if (isValid()) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (bingo[i][j]) System.out.printf("#");
else System.out.printf(".");
}
System.out.println();
}
System.out.println("_______");
}
return;
}
int r = cnt / 5;
int c = cnt % 5;
bingo[r][c] = true;
solve(cnt+1);
bingo[r][c] = false;
solve(cnt+1);
}
static boolean isValid() {
// 각각의 행, 열이 빙고인지 저장하는 변수
boolean[] rowBingo = new boolean[5];
Arrays.fill(rowBingo, true);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
rowBingo[i] &= bingo[i][j];
}
}
boolean[] colBingo = new boolean[5];
Arrays.fill(colBingo, true);
for (int j = 0; j < 5; j++) {
for (int i = 0; i < 5; i++) {
colBingo[j] &= bingo[i][j];
}
}
// 각각의 대각선이 빙고인지 저장하는 변수
boolean A1E5Bingo = bingo[0][0] && bingo[1][1] && bingo[2][2] && bingo[3][3] && bingo[4][4];
boolean A5E1Bingo = bingo[0][4] && bingo[1][3] && bingo[2][2] && bingo[3][1] && bingo[4][0];
// 행 빙고 수, 열 빙고 수, 대각선 빙고 수
int rowCnt = 0, colCnt = 0, digCnt = 0;
int[][] isBingo = new int[5][5];
for (int i = 0; i < 5; i++) {
if (rowBingo[i]) {
rowCnt++;
for (int j = 0; j < 5; j++) {
isBingo[i][j]++;
}
}
if (colBingo[i]) {
colCnt++;
for (int j = 0; j < 5; j++) {
isBingo[j][i]++;
}
}
}
if (A1E5Bingo) {
digCnt++;
for (int i = 0; i < 5; i++) {
isBingo[i][i]++;
}
}
if (A5E1Bingo) {
digCnt++;
for (int i = 0; i < 5; i++) {
isBingo[i][4-i]++;
}
}
// 직접 모든 조건 확인
if ((bingo[0][0] ^ !A5E1Bingo)) return false;
if ((bingo[0][1] ^ !(rowBingo[0] || colBingo[1]))) return false;
if ((bingo[0][2] ^ A1E5Bingo)) return false;
if ((bingo[0][3] ^ bingo[3][3])) return false;
if ((bingo[0][4] ^ (rowBingo[0] || colBingo[4] || A5E1Bingo))) return false;
if (bingo[1][0] ^ !bingo[3][0]) return false;
if (bingo[1][1] ^ (rowCnt > 0 && colCnt > 0 && digCnt > 0)) return false;
// C2: 참거짓 상관 없음
int total = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (bingo[i][j]) total++;
}
}
if (bingo[1][3] ^ (total <= 17)) return false;
int isPart = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (isBingo[i][j] > 0) isPart++;
}
}
if (bingo[1][4] ^ (isPart % 2 == 0)) return false;
if (bingo[2][0] ^ (isBingo[2][0] > 0)) return false;
int isColoredAndNotPart = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (isBingo[i][j] == 0 && bingo[i][j]) isColoredAndNotPart++;
}
}
if (bingo[2][1] ^ (isColoredAndNotPart >= 5)) return false;
if (bingo[2][2] ^ (!bingo[2][2] || isBingo[2][2] > 0)) return false;
if (bingo[2][3] ^ colCnt >= 2) return false;
if (bingo[2][4] ^ (25 - isPart >= 10)) return false;
if (bingo[3][0] ^ !bingo[1][0]) return false;
if (bingo[3][1] ^ (rowBingo[1] || colBingo[3])) return false;
int cColered = 0;
for (int i = 0; i < 5; i++) {
if (bingo[i][2]) cColered++;
}
if (bingo[3][2] ^ (cColered <= 3)) return false;
if (bingo[3][3] ^ bingo[0][3]) return false;
if (bingo[3][4] ^ (digCnt > 0)) return false;
if (bingo[4][0] ^ bingo[4][4]) return false;
// B5는 나중에 고려한다.
// C5: 참거짓 상관 없음
if (bingo[4][3] ^ (rowCnt + colCnt + digCnt >= 3)) return false;
if (bingo[4][4] ^ bingo[4][0]) return false;
return true;
}
}
|
cs |
정답
|
1
2
3
4
5
|
.#..#
#####
..#.#
.##.#
#..##
|
cs |
'PS > Implementation' 카테고리의 다른 글
| 백준 19237번: 어른 상어 (Java) (0) | 2022.07.07 |
|---|---|
| 백준 2174번: 로봇 시뮬레이션 (Java) (0) | 2022.06.30 |
| 백준 4991번: 로봇 청소기 (Java) (0) | 2022.06.27 |
| 백준 20057번: 마법사 상어와 토네이도 (Java) (0) | 2022.06.10 |
| 백준 25239번: 가희와 카오스 파풀라투스 (Java) (0) | 2022.06.09 |