𝝅번째 알파카의 개발 낙서장

screen

[백준 / JAVA] 백준 알고리즘 1014번 컨닝

posts

알고리즘

시리즈 톺아보기

백준 알고리즘

백준 알고리즘
count

컨닝 🔗

랭크 사용 언어
image JAVA

🔗 전체 1014번 문제

조건 🔗

시간제한 메모리 제한
2초 512MB

문제 🔗

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

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

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

image

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

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

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

입력 🔗

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

첫 번째 부분에서는 교실의 세로길이 N과 가로길이 M이 한 줄에 주어진다.

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

출력 🔗

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

케이스 🔗

예제 1 🔗

  • 입력

TC

04
12 3
2...
3...
42 3
5x.x
6xxx
72 3
8x.x
9x.x
1010 10
11....x.....
12..........
13..........
14..x.......
15..........
16x...x.x...
17.........x
18...x......
19........x.
20.x...x....
  • 출력

TC

04
11
22
346

풀이 🔗

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

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

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

문제 분석하기 🔗

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

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

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

image

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

image

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

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

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

image

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

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

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

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

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

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

image

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

image

버텍스 의 경우, 대다수의 노드를 포함하고 있지만 , , 노드를 포함하지 않으므로 버텍스 만으로는 최소 버텍스 커버 조합이 될 수 없다.

image

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

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

image

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

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

image

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

image

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

image

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

이분 매칭 🔗

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

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

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

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

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

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

image

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

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

image

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

image

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

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

이분 그래프의 최대 매칭 조합
위 그래프의 최대 매칭 조합은 , , , 으로 최대 매칭의 수는 2이며 4가지 경우의 수가 존재한다.

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

image

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

image

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

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

전체 소스 🔗

JAVA

0import java.io.BufferedReader;
1import java.io.BufferedWriter;
2import java.io.IOException;
3import java.io.InputStreamReader;
4import java.io.OutputStreamWriter;
5import java.util.Arrays;
6
7/**
8 * 백준 전체 1014 문제 알고리즘 클래스
9 *
10 * @author RWB
11 * @see <a href="https://blog.itcode.dev/posts/2021/06/18/a1014">1014 풀이</a>
12 * @since 2021.06.18 Fri 16:42:44
13 */
14public class Main
15{
16 // 교실 세로 길이 (y)
17 private static int N;
18
19 // 교실 가로 길이 (x)
20 private static int M;
21
22 // 자리 번호
23 private static int[][] room;
24
25 // 컨닝 가능한 자리
26 private static boolean[][] nodes;
27
28 // 방문 횟수
29 private static int visitCount;
30
31 // 버텍스별 방문 횟수
32 private static int[] visit;
33
34 // 버텍스 매칭 여부
35 private static int[] matched;
36
37 /**
38 * 메인 함수
39 *
40 * @param args: [String[]] 매개변수
41 *
42 * @throws IOException 데이터 입출력 예외
43 */
44 public static void main(String[] args) throws IOException
45 {
46 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
47 BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
48
49 // 현재 자리에서 컨닝이 가능한 자리의 위치 상대좌표
50 int[][] scopes = { { -1, 1 }, { -1, 0 }, { -1, -1 }, { 1, 1 }, { 1, 0 }, { 1, -1 } };
51
52 // 케이스 수
53 int C = Integer.parseInt(reader.readLine());
54
55 while (C-- > 0)
56 {
57 String[] temp = reader.readLine().split(" ");
58
59 N = Integer.parseInt(temp[0]);
60 M = Integer.parseInt(temp[1]);
61
62 // 자리의 파손 여부
63 boolean[][] canSit = new boolean[N][M];
64
65 // 자리의 번호
66 int numbering = 1;
67
68 // 파손된 자리의 총 갯수
69 int broken = 0;
70
71 room = new int[N][M];
72 nodes = new boolean[N * M][N * M];
73
74 visitCount = 1;
75
76 for (int n = 0; n < N; n++)
77 {
78 temp = reader.readLine().split("");
79
80 for (int m = 0; m < M; m++)
81 {
82 // 자리 번호 기록
83 room[n][m] = numbering++;
84
85 // 앉을 수 있는 경우
86 if (temp[m].equals("."))
87 {
88 canSit[n][m] = true;
89 }
90
91 // 파손된 경우
92 else
93 {
94 canSit[n][m] = false;
95
96 // 파손 갯수 1 추가
97 broken++;
98 }
99 }
100 }
101
102 for (int n = 0; n < N; n++)
103 {
104 // 홀수 열만 대상으로 동작함
105 for (int m = 0; m < M; m += 2)
106 {
107 // 앉을 수 있는 좌석일 경우
108 if (canSit[n][m])
109 {
110 for (int[] scope : scopes)
111 {
112 // 컨닝 가능성 있는 자리의 상대좌표
113 int no = n + scope[1];
114 int mo = m + scope[0];
115
116 // 상대좌표가 교실을 벗어나지 않으면서, 앉을 수 있을 경우
117 if (no > -1 && mo > -1 && no < N && mo < M && canSit[no][mo])
118 {
119 // 노드 연결 표시
120 nodes[room[n][m] - 1][room[no][mo] - 1] = true;
121 }
122 }
123 }
124 }
125 }
126
127 int result = bipartite();
128
129 writer.write(Integer.toString(N * M - broken - result));
130 writer.newLine();
131 writer.flush();
132 }
133
134 writer.close();
135 reader.close();
136 }
137
138 /**
139 * 이분 매칭 갯수 반환 함수
140 *
141 * @return [int] 이분 매칭 갯수
142 */
143 private static int bipartite()
144 {
145 // 매칭 갯수
146 int size = 0;
147
148 visit = new int[N * M];
149
150 matched = new int[N * M];
151
152 Arrays.fill(matched, -1);
153
154 for (int n = 0; n < N; n++)
155 {
156 for (int m = 0; m < M; m += 2)
157 {
158 visitCount++;
159
160 size += dfs(room[n][m] - 1);
161 }
162 }
163
164 return size;
165 }
166
167 /**
168 * DFS 알고리즘 결과 반환 함수
169 *
170 * @param num: [int] 시작점
171 *
172 * @return [int] 매칭 갯수
173 */
174 private static int dfs(int num)
175 {
176 // 같은 버텍스가 아닐 경우
177 if (visit[num] != visitCount)
178 {
179 visit[num] = visitCount;
180
181 for (int i = 0; i < N * M; i++)
182 {
183 // num과 i 버텍스 사이에 노드가 존재할 경우
184 if (nodes[num][i])
185 {
186 // 아직 매칭되지 않았거나, 이미 i와 매칭된 버텍스가 다른 버텍스와 매칭할 수 있을 경우
187 if (matched[i] == -1 || dfs(matched[i]) == 1)
188 {
189 matched[i] = num;
190
191 return 1;
192 }
193 }
194 }
195 }
196
197 return 0;
198 }
199}

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

JAVA

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

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

JAVA

0private static int dfs(int num)
1{
2 // 같은 버텍스가 아닐 경우
3 if (visit[num] != visitCount)
4 {
5 visit[num] = visitCount;
6
7 for (int i = 0; i < N * M; i++)
8 {
9 // num과 i 버텍스 사이에 노드가 존재할 경우
10 if (nodes[num][i])
11 {
12 // 아직 매칭되지 않았거나, 이미 i와 매칭된 버텍스가 다른 버텍스와 매칭할 수 있을 경우
13 if (matched[i] == -1 || dfs(matched[i]) == 1)
14 {
15 matched[i] = num;
16
17 return 1;
18 }
19 }
20 }
21 }
22
23 return 0;
24}

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

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

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

비공식 케이스 🔗

  • 입력

TC

01
110 10
2.X.X...X..
3.X..X.....
4X.X.......
5.X.X......
6X...X.....
7.X.X...X..
8.X..X.....
9X.X.......
10.X.X......
11X...X.....
  • 출력

TC

042
  • 입력

TC

01
15 10
2.X.X...X..
3.X..X.....
4X.X.......
5.X.X......
6X...X.....
  • 출력

TC

021
  • 입력

TC

01
15 8
2.X...X..
3..X.....
4X.......
5.X......
6..X.....
  • 출력

TC

018
  • 입력

TC

01
15 7
2X...X..
3.X.....
4.......
5X......
6.X.....
  • 출력

TC

017

분류 🔗

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

여담 🔗

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

참고 🔗