컨닝

---

🔗 🔗 전체 1014번 문제

조건

---

문제

---

최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한다.

시험은 $N$행 $\times$ $M$열 크기의 직사각형 교실에서 이루어진다. 교실은 $1 \times 1$ 크기의 단위 정사각형으로 이루어져 있는데, 각 단위 정사각형은 자리 하나를 의미한다.

최백준은 컨닝을 방지하기 위해서 다음과 같은 전략을 세웠다. 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위, 이렇게 총 네 자리에 앉아있는 친구의 답지를 항상 베낀다고 가정한다. 따라서, 자리 배치는 모든 학생이 컨닝을 할 수 없도록 배치되어야 한다.

위의 그림을 보자. $A$, $C$, $D$ 혹은 $E$에 다른 학생을 앉히는 것은 좋은 생각이 아니다. 그 이유는 이미 앉아있는 학생이 그들의 답안지를 베낄 우려가 있기 때문이다. 하지만, $B$에 다른 학생을 앉힌다면, 두 학생은 서로의 답지를 베낄 수 없어 컨닝의 우려가 없다.

위와 같이 컨닝이 불가능하도록 자리를 배치 하려는 최백준의 행동에 분노한 일부 학생들이 교실의 책상을 부숴버렸기 때문에, 일부 자리에는 학생이 앉을 수 없다.

최백준은 교실의 모양이 주어졌을 때, 이 곳에서 아무도 컨닝을 할 수 없도록 학생을 배치하였을 경우에 교실에 배치할 수 있는 최대 학생 수가 몇 명인지 궁금해졌다. 최백준을 위해 이를 구하는 프로그램을 작성하라.

입력

---

입력의 첫 줄에는 테스트케이스의 개수 $C$가 주어진다. 각각의 테스트 케이스는 아래와 같이 두 부분으로 이루어진다.

첫 번째 부분에서는 교실의 세로길이 N과 가로길이 M이 한 줄에 주어진다. $(1 ≤ M ≤ 10, 1 ≤ N ≤ 10)$

두 번째 부분에서는 정확하게 N줄이 주어진다. 그리고 각 줄은 M개의 문자로 이루어져있다. 모든 문자는 ‘.’(앉을 수 있는 자리) 또는 ‘x’(앉을 수 없는 자리, 소문자)로 구성된다.

출력

---

각각의 테스트 케이스에 대해 그 교실에서 시험을 볼 수 있는 최대 학생의 수를 출력한다.

케이스

---

예제 1

---

• 입력

TC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

• 출력

TC
1
2
3
4
4
1
2
46

풀이

---

또 한번의 플래티넘 문제. 하....

문제 이름 그대로 컨닝을 못 참게 만드는 문제다. 문제를 푸는 방식에는 두 가지가 있다. 네트워크 플로우와 비트마스킹. 본 포스팅에서는 네트워크 플로우 방식을 차용한다. 이게 정석이라고 하기도 하고, JAVA 풀이는 죄다 비트마스킹 방식이라서.

나 같이 전공지식이 전무한 코더에게는 너무나도 가혹한 문제다. 지금까지 살면서 하나 깨달은 게 있다면, 아무리 처음 보는 개념이라도 계속 쳐다보면 언젠가 이해된다. 하루가 됐든 한 달이 됐든. 그 난리를 펴가며 이해한 내용은 아래와 같다.

문제 분석하기

---

문제 해결에 영향을 미치는 조건은 아래와 같다.

1. 임의의 자리를 기준으로 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위 자리를 컨닝할 수 있다.
2. 파손되어 앉을 수 없는 자리가 존재한다.

임의의 자리가 있다고 가정하고 이를 도식화해보자.

위 사진과 같이 특정 자리를 기준으로 자신의 주변엔 최대 8개의 자리가 존재할 수 있다. 1번 규칙에 따라 컨닝이 가능한 자리를 도식하면 아래와 같다.

컨닝 가능한 자리는 위와 같이 6개로 표시된다. 엥? 분명히 1번 규칙에서는 특정 자리를 기준으로 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위만 가능하다고 했다. 해당 규칙에 따르면 4개 자리여야 할텐데, 왼쪽 대각선 아래, 오른쪽 대각선 아래는 왜 해당되는걸까?

특정 자리에서 왼쪽 대각선 아래, 오른쪽 대각선 아래를 컨닝할 순 없지만, 반대로 왼쪽 대각선 아래, 오른쪽 대각선 아래에선 특정 자리를 컨닝할 수 있기 때문. 컨닝을 할 수 있는 자리와 당할 수 있는 자리 모두를 고려해야한다.

반대로 컨닝이 불가능한 자리를 도식하면 아래와 같다.

컨닝이 불가능한 자리는 위와 같이 2개로 표시된다. 자신의 앞 뒤는 컨닝할 수 없다. 우리가 설계한 알고리즘이 이와 같은 결과를 계산할 수 있어야 한다. 그렇다면 이를 어떤 방법으로 해결할 수 있을까?

이 문제를 해결하는 방법은 크게 두 가지가 있다.

1. 최소 버텍스 커버, 이분 매칭
2. DP, 비트마스킹

이 중 1번 최소 버텍스 커버와 이분 매칭을 사용하여 풀고자 한다.

Miminum Vertex Cover(최소 버텍스 커버)

---

Miminum Vertex Cover(최소 버텍스 커버)는 모든 노드가 연결된 점(Vertex)의 최소 집합을 의미한다. 예를 들어, 아래와 같은 그림이 있다고 가정하자.

위 사진에서의 $A$ ~ $I$에 해당하는 9개 점이 Vertex, 각 점마다 연결된 선이 노드가 된다. 버텍스가 모든 노드를 커버할 수 있다면 버텍스 커버라 볼 수 있다. 그 중 모든 노드를 커버하는 가작 적은 버텍스의 집합이 Miminum Vertex Cover(최소 버텍스 커버)라 할 수 있다.

버텍스 $E$의 경우, 대다수의 노드를 포함하고 있지만 $\overline{AB}$, $\overline{BC}$, $\overline{FI}$ 노드를 포함하지 않으므로 버텍스 $E$만으로는 최소 버텍스 커버 조합이 될 수 없다.

위와 같이 $B$, $F$ 버텍스를 포함할 경우 존재하는 모든 노드를 포함하는 가장 적은 버텍스의 조합이므로 최소 버텍스 커버가 된다.

유의깊게 봐야할 점은, 최소 버텍스 커버를 통해 최대 독립 집합을 구할 수 있다. 최소 버텍스 커버에 해당하는 버텍스와 모든 노드를 제거해보자. 아래와 같이 도식할 수 있다.

이처럼, 전체 그룹에서 최소 버텍스 커버를 제거하면 나머지 버텍스들은 그 어떤 버텍스끼리도 연결되지 않는 독립 버텍스다. 최소 버텍스 커버가 모든 노드를 연결한 버텍스의 최소 집함임을 생각한다면, 이를 뺀 나머지는 어떤 버텍스와도 연결되지 않는 버텍스 집합의 최대 조합이라고 할 수 있다. 즉, 최대 독립 집합 $=$ 전체 그룹 $-$ 최소 버텍스 커버로 표현할 수 있다.

그래, 그건 그렇다 치고, 위 개념이 이 문제와 무슨 연관성이 있길래 이렇게 장황하게 서술할까? 이번엔 조금 다르게 이 문제와 연관지어 예시를 들어본다.

그 어떤 자리도 파손되지 않은 온전한 9개 자리가 있다고 가정하자. 각 자리별로 컨닝이 가능한 자리를 노드로 연결하면 위와 같이 도식할 수 있다.

위 사진에서 최소 버텍스 커버는 $B$, $E$, $H$가 된다. 이 자리 3개로 위 사진의 모든 노드를 포함할 수 있기 때문이다. 이 자리들을 제거하여 최대 독립 집합을 표현하면 어떻게 될까?

나머지 자리인 $A$, $C$, $D$, $F$, $G$, $H$만 남게 되며, 각 자리는 그 어떤 노드와도 연결되어있지 않다. 이 사진에서의 노드는 컨닝 가능한 자리이므로, 노드가 없다는 것은 컨닝할 수 있는 자리가 없다는 뜻이 된다. 즉, 최소 버텍스 커버 로직을 설계하는 것이 이번 알고리즘의 키 포인트다.

이분 매칭

---

자, 최소 버텍스 커버가 알고리즘의 키인 건 알았으니, 이를 구현하기만 하면 된다. 안타깝게도 최소 버텍스 커버를 코딩으로 계산하는 것은 매우 복잡한 일이다.

König's Theorem(쾨닉의 정리)에 의하면 모든 이분 그래프의 최대 매칭은 최소 버텍스 커버와 같다고 증명한다. 즉, 위 그래프를 이분 그래프로 변경하여 최대 매칭을 구하면 최소 버텍스 커버를 구할 수 있다는 뜻이다.

결론적으로, 최소 버텍스 커버를 구하기 위해 이분 매칭 알고리즘을 구현해야 한다.

이분 매칭의 연산에 사용하는 이분 그래프는 아래와 같은 특징을 가진다.

• 모든 정점을 두 그룹으로 나눌 수 있다.
• 모든 노드는 한 그룹에서 다른 그룹으로 연결된다.
• 같은 그룹끼리는 연결되지 않는다.

고등수학을 배웠다면 우리는 이미 이분 그래프를 접한적이 있다.

위 사진은 임의의 함수 $f(x)$에 대한 식을 도식화한 것이다. 위 함수 도식은 이분 그래프의 적절한 예시가 될 수 있다. 모든 그룹이 $x$ 혹은 $y$그룹으로 나뉘며, 모든 노드가 $x$에서 $y$로 연결된다.

이분 그래프의 매칭은 각 그룹의 버텍스를 매칭하는 노드의 집합이다. 단, 각 노드의 끝 점은 다른 노드와 중복되지 않는다. 이분 그래프의 최대 매칭은 이분 그래프의 매칭의 노드 수가 최대인 조합이다.

위와 같이 연결된 이분 그래프가 있다고 가정하자. $1$번 버텍스를 기준으로 $A$와 $B$에 노드가 연결되어있다. $\overline{A1}$을 선택할 경우, $\overline{B1}$은 매칭에서 제외된다. 노드의 끝 선이 $1$번 버텍스로 동일하기 때문이다. 각 노드의 끝 점은 다른 노드와 중복되지 않는다는 말의 의미는 이와 같다.

1. $A$와 $1$번 버텍스를 잇는 노드 $\overline{A1}$을 선택한다.
2. $B$와 $1$번 버텍스를 잇는 노드 $\overline{B1}$은 노드 $\overline{A1}$이 $1$번 버텍스를 포함하므로 선택할 수 없다.
3. 노드 $\overline{A1}$의 시작 버텍스인 $A$에부터 다른 노드가 있는지 탐색한다.
4. $A$ 버텍스와 연결된 다른 노드가 없으므로 노드 $\overline{A1}$의 선택을 유지한다.
5. $C$와 $1$번 버텍스를 잇는 노드 $\overline{C1}$을 선택한다.
6. 마지막 버텍스이므로 탐색을 종료하고 갯수를 계산한다.

이와 같은 과정으로 이분 그래프의 최대 매칭의 수는 2가 된다. 물론 최대 매칭의 조합은 여러개가 될 수 있겠지만, 이 알고리즘에선 "조합"이 아니라 "수"가 중요하므로 경우의 수를 구할 필요는 없다.

이분 매칭을 문제에 적용하면 아래와 같다.

이번엔 조금 복합적인 예시다. 버텍스 $A$와 $E$가 파손되어 앉을 수 없는 상황이다. 이러한 조건에서 컨닝 가능한 자리를 노드로 표현하면 위 사진과 같이 표현할 수 있다. 규칙의 특성 상, 한 쪽 열은 양 옆의 열에 영향을 준다. 즉, 홀수열과 짝수열로 그룹을 나눌 수 있다. 열의 홀짝을 기준으로 나눠 이분 그래프를 표시하면 아래와 같다.

위 이분 그래프의 최대 매칭은 2가 된다. 즉, 최소 버텍스 커버의 조합은 $B$, $H$고 파손되서 착석이 불가능한 자리는 $A$, $E$가 된다. 따라서 $C$, $D$, $F$, $G$, $I$가 컨닝 불가능한 자리가 된다. 단순히 자리의 "수"만 계산하면 되므로 컨닝 불가능한 자리 = 전체 자리 - 최소 버텍스 커버 수 - 파손된 자리가 된다. 따라서 위 그래프의 알고리즘 수행 결과는 5가 된다.

이분 매칭은 BFS(Breadth First Search, 너비 우선 탐색) 혹은 DFS(Depth First Search, 깊이 우선 탐색)으로 구현할 수 있다.

전체 소스

---

JAVA
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 백준 전체 1014 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/18/a1014">1014 풀이</a>
 * @since 2021.06.18 Fri 16:42:44
 */
public class Main
{
	// 교실 세로 길이 (y)
	private static int N;
	
	// 교실 가로 길이 (x)
	private static int M;
	
	// 자리 번호
	private static int[][] room;
	
	// 컨닝 가능한 자리
	private static boolean[][] nodes;
	
	// 방문 횟수
	private static int visitCount;
	
	// 버텍스별 방문 횟수
	private static int[] visit;
	
	// 버텍스 매칭 여부
	private static int[] matched;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 현재 자리에서 컨닝이 가능한 자리의 위치 상대좌표
		int[][] scopes = { { -1, 1 }, { -1, 0 }, { -1, -1 }, { 1, 1 }, { 1, 0 }, { 1, -1 } };
		
		// 케이스 수
		int C = Integer.parseInt(reader.readLine());
		
		while (C-- > 0)
		{
			String[] temp = reader.readLine().split(" ");
			
			N = Integer.parseInt(temp[0]);
			M = Integer.parseInt(temp[1]);
			
			// 자리의 파손 여부
			boolean[][] canSit = new boolean[N][M];
			
			// 자리의 번호
			int numbering = 1;
			
			// 파손된 자리의 총 갯수
			int broken = 0;
			
			room = new int[N][M];
			nodes = new boolean[N * M][N * M];
			
			visitCount = 1;
			
			for (int n = 0; n < N; n++)
			{
				temp = reader.readLine().split("");
				
				for (int m = 0; m < M; m++)
				{
					// 자리 번호 기록
					room[n][m] = numbering++;
					
					// 앉을 수 있는 경우
					if (temp[m].equals("."))
					{
						canSit[n][m] = true;
					}
					
					// 파손된 경우
					else
					{
						canSit[n][m] = false;
						
						// 파손 갯수 1 추가
						broken++;
					}
				}
			}
			
			for (int n = 0; n < N; n++)
			{
				// 홀수 열만 대상으로 동작함
				for (int m = 0; m < M; m += 2)
				{
					// 앉을 수 있는 좌석일 경우
					if (canSit[n][m])
					{
						for (int[] scope : scopes)
						{
							// 컨닝 가능성 있는 자리의 상대좌표
							int no = n + scope[1];
							int mo = m + scope[0];
							
							// 상대좌표가 교실을 벗어나지 않으면서, 앉을 수 있을 경우
							if (no > -1 && mo > -1 && no < N && mo < M && canSit[no][mo])
							{
								// 노드 연결 표시
								nodes[room[n][m] - 1][room[no][mo] - 1] = true;
							}
						}
					}
				}
			}
			
			int result = bipartite();
			
			writer.write(Integer.toString(N * M - broken - result));
			writer.newLine();
			writer.flush();
		}
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 이분 매칭 갯수 반환 함수
	 *
	 * @return [int] 이분 매칭 갯수
	 */
	private static int bipartite()
	{
		// 매칭 갯수
		int size = 0;
		
		visit = new int[N * M];
		
		matched = new int[N * M];
		
		Arrays.fill(matched, -1);
		
		for (int n = 0; n < N; n++)
		{
			for (int m = 0; m < M; m += 2)
			{
				visitCount++;
				
				size += dfs(room[n][m] - 1);
			}
		}
		
		return size;
	}
	
	/**
	 * DFS 알고리즘 결과 반환 함수
	 *
	 * @param num: [int] 시작점
	 *
	 * @return [int] 매칭 갯수
	 */
	private static int dfs(int num)
	{
		// 같은 버텍스가 아닐 경우
		if (visit[num] != visitCount)
		{
			visit[num] = visitCount;
			
			for (int i = 0; i < N * M; i++)
			{
				// num과 i 버텍스 사이에 노드가 존재할 경우
				if (nodes[num][i])
				{
					// 아직 매칭되지 않았거나, 이미 i와 매칭된 버텍스가 다른 버텍스와 매칭할 수 있을 경우
					if (matched[i] == -1 || dfs(matched[i]) == 1)
					{
						matched[i] = num;
						
						return 1;
					}
				}
			}
		}
		
		return 0;
	}
}

유의깊게 봐야할 코드는 아래와 같다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static int bipartite()
{
	// 매칭 갯수
	int size = 0;
	
	visit = new int[N * M];
	
	matched = new int[N * M];
	
	Arrays.fill(matched, -1);
	
	for (int n = 0; n < N; n++)
	{
		for (int m = 0; m < M; m += 2)
		{
			visitCount++;
			
			size += dfs(room[n][m] - 1);
		}
	}
	
	return size;
}

위 코드가 이분매칭을 DFS 알고리즘을 통해 구현한 것이다. for문의 변수 선언 중 m += 2인 이유는 홀수열만 체크하기 위함이다.

JAVA
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
private static int dfs(int num)
{
	// 같은 버텍스가 아닐 경우
	if (visit[num] != visitCount)
	{
		visit[num] = visitCount;
		
		for (int i = 0; i < N * M; i++)
		{
			// num과 i 버텍스 사이에 노드가 존재할 경우
			if (nodes[num][i])
			{
				// 아직 매칭되지 않았거나, 이미 i와 매칭된 버텍스가 다른 버텍스와 매칭할 수 있을 경우
				if (matched[i] == -1 || dfs(matched[i]) == 1)
				{
					matched[i] = num;
					
					return 1;
				}
			}
		}
	}
	
	return 0;
}

이분매칭을 구현하는 DFS 알고리즘의 코드는 위와 같다. matched 배열은 -1로 초기화되며, 매칭되는 버텍스의 번호를 할당받는다.

$A$ 버텍스가 $B$ 버텍스와 연결된 노드 $\overline{AB}$를 가질 경우, 이를 matched[A] = B와 같이 표시한다. 만약, $A$ 버텍스가 $B$ 버텍스를 연결하는 와중에 이미 $B$가 $C$와 연결되어있을 경우, $C$ 버텍스에 $B$가 아닌 다른 버텍스와 연결된 노드가 있는지 확인한다. 만약 가능할 경우, $\overline{BC}$를 제거하고 $C$와 연결할 수 있는 다른 버텍스를 연결한다. 이후 $\overline{AB}$를 연결한다.

이 과정을 반복하여 연결을 수립할 수 있을 경우 1, 없을 경우 0을 반환한다. 이는 boolean 타입으로도 대체할 수 있으나, dfs()연산 결과를 더하기 때문에 편의상 int로 반환한다.

비공식 케이스

---

• 입력

TC
1
2
3
4
5
6
7
8
9
10
11
12
1
10 10
.X.X...X..
.X..X.....
X.X.......
.X.X......
X...X.....
.X.X...X..
.X..X.....
X.X.......
.X.X......
X...X.....

• 출력

TC
1
42

• 입력

TC
1
2
3
4
5
6
7
1
5 10
.X.X...X..
.X..X.....
X.X.......
.X.X......
X...X.....

• 출력

TC
1
21

• 입력

TC
1
2
3
4
5
6
7
1
5 8
.X...X..
..X.....
X.......
.X......
..X.....

• 출력

TC
1
18

• 입력

TC
1
2
3
4
5
6
7
1
5 7
X...X..
.X.....
.......
X......
.X.....

• 출력

TC
1
17

분류

---

• 다이나믹 프로그래밍
• 비트마스킹
• 최대 유량
• 비트필드를 이용한 다이나믹 프로그래밍

여담

---

🔗 습격자 초라기가 매우 복잡한 케이스들을 이해하는데 할애했다면, 이 문제는 케이스가 복잡하다기 보단, 네트워크 플로우를 이해하고 적용하는데 대부분의 시간을 할애했다. 문제 보니까 가면 갈수록 플래티넘이 계속해서 나오는 구간도 있던데, 순서대로 푸는 규칙에 대해 진지하게 생각해봐야하나 싶다.

참고

---

• 🔗 개발괴발
• 🔗 Crocus