🔗 Full Problem 1014

Professor Choi Baekjoon teaches a course called "The Art of Cheating" at Sogang University. This course has a solid reputation for being quite tricky, so some students try to copy other people's answers during exams.

The exam takes place in a rectangular classroom that is $N$ rows by $M$ columns in size. The classroom is made up of unit squares of size $1 \times 1$, each representing one seat.

To prevent cheating, Choi Baekjoon devised the following strategy. Assume that every student always copies the answers of whoever sits to their left, right, diagonally up-left, or diagonally up-right — four seats in total. Therefore, the seating arrangement must be laid out so that no student is able to cheat.

Look at the image above. It's a bad idea to seat another student at $A$, $C$, $D$, or $E$. That's because there's a risk that the student already seated there could copy their answers. However, if you seat another student at $B$, neither student can copy the other's answers, so there's no risk of cheating.

Since some students got angry at Choi Baekjoon's attempt to arrange seats so that cheating is impossible and destroyed some of the classroom's desks, students cannot sit in certain seats.

Given the shape of a classroom, Choi Baekjoon became curious about the maximum number of students that can be seated in this classroom such that no cheating is possible. Write a program to compute this for him.

The first line of input gives the number of test cases $C$. Each test case consists of two parts, as described below.

In the first part, the classroom's height N and width M are given on a single line. $(1 ≤ M ≤ 10, 1 ≤ N ≤ 10)$

In the second part, exactly N lines follow. Each line consists of M characters. Every character is either '.' (a seat that can be sat in) or 'x' (a seat that cannot be sat in, lowercase).

For each test case, print the maximum number of students who can take the exam in that classroom.

• Input

TC
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....

• Output

TC
4
1
2
46

Yet another Platinum problem. Ugh...

True to its name, this problem tests your patience with cheating. There are two ways to solve this problem: network flow and bitmasking. This post adopts the network flow approach — partly because it's said to be the "proper" way, and partly because every JAVA solution I found used bitmasking.

For a coder with essentially no formal CS background like myself, this is a brutally tough problem. If there's one thing I've learned in life, it's that no matter how unfamiliar a concept seems at first, if you keep staring at it long enough, you'll eventually understand it — whether that takes a day or a month. Here's what I understood after going through that whole ordeal.

The conditions that affect how to solve this problem are as follows.

1. From any given seat, you can cheat off the seats to your left, right, diagonally up-left, and diagonally up-right.
2. Some seats are broken and cannot be sat in.

Let's assume there's an arbitrary seat and diagram this out.

As shown in the image above, around any given seat, there can be up to 8 surrounding seats. If we diagram the seats from which cheating is possible according to rule 1, it looks like this.

The seats from which cheating is possible are marked as 6 seats above. Wait, what? Rule 1 clearly said that, based on the given seat, only the left, right, diagonal up-left, and diagonal up-right seats apply. According to that rule, there should only be 4 seats — so why are the diagonal down-left and diagonal down-right seats included too?

While the given seat cannot cheat off the diagonal down-left or diagonal down-right seats, conversely, those diagonal down-left and diagonal down-right seats CAN cheat off the given seat. You have to consider both the seats that can cheat and the seats that can be cheated off of.

Conversely, if we diagram the seats where cheating is not possible, it looks like this.

The seats where cheating is not possible are the 2 marked above. The seats directly in front of and behind you can't be cheated off of. The algorithm we design needs to be able to compute a result like this. So how can we solve this?

There are broadly two ways to solve this problem.

1. Minimum vertex cover, bipartite matching
2. DP, bitmasking

Of these, I'll solve it using approach 1: minimum vertex cover and bipartite matching.

Minimum Vertex Cover refers to the smallest set of vertices such that every edge is connected to at least one vertex in the set. For example, suppose we have the following diagram.

In the image above, the 9 points $A$ through $I$ are the vertices, and each line connecting them is an edge. If a set of vertices covers every edge, it's called a vertex cover. Among all such sets, the smallest set of vertices that covers every edge is called the Minimum Vertex Cover.

Vertex $E$ alone covers most of the edges, but it doesn't cover edges $\overline{AB}$, $\overline{BC}$, or $\overline{FI}$, so vertex $E$ alone cannot be a minimum vertex cover.

As shown above, including vertices $B$ and $F$ covers every existing edge with the smallest possible combination of vertices, making it a minimum vertex cover.

One thing worth paying close attention to is that you can derive the maximum independent set from the minimum vertex cover. Let's remove the vertices belonging to the minimum vertex cover along with all their edges. It can be diagrammed as follows.

As shown, if you remove the minimum vertex cover from the whole group, the remaining vertices form an independent set with no edges connecting any of them. Since the minimum vertex cover is the smallest set of vertices that covers every edge, the remaining vertices form the largest possible set of vertices with no edges among them. In other words, it can be expressed as: Maximum Independent Set $=$ Total Group $-$ Minimum Vertex Cover.

Okay, fine, but how does this concept relate to this problem, that it deserves such a lengthy explanation? Let's try a slightly different example, connected directly to this problem.

Suppose there are 9 intact seats, none of them broken. If we connect the seats from which cheating is possible with edges for each seat, it can be diagrammed as above.

In the image above, the minimum vertex cover is $B$, $E$, $H$. These 3 seats cover every edge in the image above. What happens if we remove these seats to express the maximum independent set?

What remains are the seats $A$, $C$, $D$, $F$, $G$, $H$, and none of them are connected to any edge. Since the edges in this picture represent seats from which cheating is possible, having no edges means there's no seat from which you can cheat. In other words, designing the logic for minimum vertex cover is the key point of this algorithm.

Now that we know minimum vertex cover is the key to the algorithm, all we need to do is implement it. Unfortunately, computing minimum vertex cover in code is a very complex task.

König's Theorem proves that the maximum matching of any bipartite graph equals its minimum vertex cover. In other words, if we convert the graph above into a bipartite graph and find its maximum matching, we can obtain the minimum vertex cover.

In conclusion, to find the minimum vertex cover, we need to implement a bipartite matching algorithm.

The bipartite graph used in bipartite matching computations has the following characteristics.

• All vertices can be divided into two groups.
• Every edge connects a vertex in one group to a vertex in the other group.
• Vertices within the same group are never connected.

If you've studied high school math, you've already encountered bipartite graphs before.

The image above diagrams an equation for some arbitrary function $f(x)$. This function diagram is a good example of a bipartite graph. Every group is divided into either the $x$ group or the $y$ group, and every edge connects from $x$ to $y$.

A matching of a bipartite graph is a set of edges that matches vertices from each group, with the constraint that no vertex is an endpoint of more than one edge in the set. The maximum matching of a bipartite graph is the matching combination with the largest possible number of edges.

Suppose we have a connected bipartite graph as shown above. Based on vertex $1$, edges connect to both $A$ and $B$. If we select $\overline{A1}$, then $\overline{B1}$ is excluded from the matching, because both edges share the same endpoint at vertex $1$. This is what it means for no vertex to be an endpoint of more than one edge.

1. Select edge $\overline{A1}$, connecting $A$ and vertex $1$.
2. Edge $\overline{B1}$, connecting $B$ and vertex $1$, cannot be selected because edge $\overline{A1}$ already includes vertex $1$.
3. Search from $A$, the starting vertex of edge $\overline{A1}$, to see if there's another edge available.
4. Since there's no other edge connected to vertex $A$, keep the selection of edge $\overline{A1}$.
5. Select edge $\overline{C1}$, connecting $C$ and vertex $1$.
6. Since this is the last vertex, end the search and count the total.

Through this process, the maximum matching count of the bipartite graph turns out to be 2. Of course, there can be multiple combinations that achieve the maximum matching, but in this algorithm, what matters is the "count," not the "combination," so there's no need to enumerate all possible combinations.

Maximum matching combinations of the bipartite graph
The maximum matching combinations of the graph above are $[ \overline{A1}, \overline{C2} ]$, $[ \overline{A1}, \overline{C3} ]$, $[ \overline{B1}, \overline{C2} ]$, $[ \overline{B1}, \overline{C3} ]$ — the maximum matching count is 2, and there are 4 possible combinations.

Applying bipartite matching to this problem looks like this.

This time, let's use a somewhat more complex example. Vertices $A$ and $E$ are broken and cannot be sat in. Under these conditions, if we represent the seats from which cheating is possible as edges, it looks like the image above. Due to the nature of the rule, one column affects the columns on either side of it. In other words, we can divide the columns into odd and even groups. If we divide by whether the column index is odd or even and draw the bipartite graph, it looks like this.

The maximum matching of the bipartite graph above is 2. In other words, the minimum vertex cover combination is $B$, $H$, and the seats that are broken and unseatable are $A$, $E$. Therefore, $C$, $D$, $F$, $G$, $I$ are seats where cheating is not possible. Since we only need to compute the "count" of seats, this can be expressed as seats where cheating is not possible = total seats - minimum vertex cover count - broken seats. Therefore, the result of running the algorithm on the graph above is 5.

Bipartite matching can be implemented using either BFS (Breadth First Search) or DFS (Depth First Search).

JAVA
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;
	}
}

The code worth paying close attention to is below.

JAVA
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;
}

The code above implements bipartite matching using a DFS algorithm. The reason the for loop variable is declared with m += 2 is to check only the odd-indexed columns.

JAVA
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;
}

The code for the DFS algorithm that implements bipartite matching is shown above. The matched array is initialized to -1, and each element gets assigned the number of the vertex it's matched with.

If vertex $A$ has an edge $\overline{AB}$ connecting it to vertex $B$, this is recorded as matched[A] = B. If, while connecting vertex $A$ to vertex $B$, $B$ turns out to already be connected to $C$, we check whether vertex $C$ has another edge connecting to some vertex other than $B$. If it's possible, we remove edge $\overline{BC}$ and connect $C$ to another available vertex instead. Then we connect $\overline{AB}$.

Repeating this process, if a connection can be established, it returns 1; otherwise, it returns 0. This could also be represented as a boolean, but since the results of dfs() calls are summed, it's returned as an int for convenience.

• Input

TC
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.....

• Output

TC
42

• Input

TC
1
5 10
.X.X...X..
.X..X.....
X.X.......
.X.X......
X...X.....

• Output

TC
21

• Input

TC
1
5 8
.X...X..
..X.....
X.......
.X......
..X.....

• Output

TC
18

• Input

TC
1
5 7
X...X..
.X.....
.......
X......
.X.....

• Output

TC
17

• Dynamic Programming
• Bitmasking
• Maximum Flow
• Dynamic Programming with Bitfields

While The Raiders of Cho-la-gi required most of my effort just to understand its very complex cases, this problem's cases weren't so much complex as they were time-consuming to understand and apply network flow to. Looking at the problem list, there seems to be a stretch where platinum-rated problems keep appearing one after another, so I'm starting to seriously wonder whether solving them in order is really the right approach.

• Devgoefeol
• Crocus