https://www.acmicpc.net/problem/1014
오랜만에 알고리즘 글을 올리게 되네요. 저번 학기가 너무 여유가 없었어서 꾸준히 올리고 싶었는데... 풀 때까지 하루종일 잡을거 생각하니 바빠서 손에서 잘 안잡히더라고요. 방학이기도 하고 충분히 쉬었다 싶어서 다시 시작해보려고 합니다.
이번 문제는 제가 이전에 점프하고 넘어갔던 1014번 컨닝입니다. 이 문제는 제가 여러번 시도를 했는데 실패했고 도저히 반례도 찾을 수가 없어서 포기한 문제입니다. 1016번까지 풀고 그래도 마저 풀고 싶다는 생각에, 이래저래 검색도 해보고 공부도 하다가 겨우겨우 풀어냈네요. 그 과정을 다 서술하고 싶지만, 그 내용이 꽤 많아서 저는 최대한 간단히 적고 개념 이해에 도움이 많이 되었던 사이트들을 링크하도록 하겠습니다.
문제를 간단히 설명하겠습니다. 시험을 보는 어떤 교실에 자리가 행(M)과 열(N)을 맞춰서 두어져 있는데 아래의 그림처럼 B 아래에 있는 자리에 앉은 학생은 A, C, D, E에 있는 학생의 시험지를 컨닝을 할 수 있습니다. 문제의 핵심은 컨닝을 하지 못하게끔 학생들을 최대한 많이 앉히는 것입니다. 중요한 점은, 모든 자리가 멀쩡한 것이 아니라 화가난 학생들이 몇몇 자리를 부숴놓기도 한다는 것이죠. 즉, 행과 열의 갯수, 자리의 상태 들을 input으로 받습니다.
언뜻 보면 간단한 문제로 보일 수 있습니다. 처음에 생각했을 땐, 그냥 짝수열과 홀수열에 멀쩡한 자리가 많은 열에만 싹 다 앉히면 되는거 아니냐고 생각을 했었는데 정답률을 보니 그리 간단하지 않을 것이란 생각과 동시에 시원하게 오답처리 되었었죠. 알고 보니 굉장히 어려운 문제였습니다.
Hint!
이 문제를 풀기 위해서는 아래와 같은 몇 가지 개념에 대한 이해가 선행되어야 합니다. 이 개념들에 대해서 간단히 설명하긴 할 것이지만, 자세한 설명은 제가 같이 걸어둔 링크를 참고하시면 더 좋을 것 같아요. 저도 여기서 공부했기 때문입니다. 먼저 개념들을 설명하고 이 문제랑 어떠한 관련이 있는지 설명할 것이니, 이 내용들을 처음 보시는 분이라면 일단 아 이런게 있군! 하시면 될 것 같아요.
1. 최대 독립집합과 최소 버텍스 커버 (https://www.crocus.co.kr/756)
최대 독립 집합은, 그래프에 속하는 정점들 중에서 서로 독립적인 정점(서로 이어진 간선이 없는 정점)을 최대한 뽑아낸 정점의 집합을 의미합니다. 이게 무슨 뜻인지 처음 들으시는 분들은 잘 와닿지 않을 수도 있는데요, 위의 그림을 먼저 봅시다. 이 그림은 정점 8개로 이루어진 그래프에서 찾을 수 있는 독립 집합들(빨간색으로 칠해진 정점들)을 나열한 것인데요, 이 점들의 특징은 서로 연결된 간선(edge)가 없다는 것입니다. 이러한 독립 집합 중, 그 정점의 수가 최대인 경우가 최대 독립 집합입니다. 위의 그림에서 최대 독립 집합은 가운데 열을 의미하게 되지요.
한편, 최소 버텍스 커버란, 모든 간선을 이을 수 있는 정점들의 집합 중, 정점의 개수가 최소가 되는 경우를 말합니다. 위의 그림은 7개의 정점으로 이루어진 그래프에서 B, G의 정점 집합이 모든 간선을 잇고 있고 정점의 수(2개)가 최소임을 간단히 알 수 있기 때문에 최소 버텍스 커버라고 말할 수 있습니다. 정점 A, G, F, E, D, C 도 버텍스 커버라고 말할 수 있지만, 최소 버텍스 커버는 아닌 겁니다. 여기서 중요한 점은, 최소 버텍스 커버의 여집합은 최대 독립 집합이 된다는 것입니다. 즉, 위 그림에서 G, B를 제외하면 A, C, D, F, E가 최대 독립 집합인 것이지요.
2. 이분 그래프와 이분 매칭 (https://www.crocus.co.kr/499)
이분 그래프란 위 그림 처럼 두 정점 집합(A, B)이 있고 집합 내의 정점끼리는 간선이 없이 모든 집합 간의 정점끼리만 간선이 있는(모든 간선의 양 끝점이 서로 다른 정점의 집합에 있는) 그래프를 말합니다. 고등학교 수학시간에 함수를 배우면서 정의역과 공역을 배우면서 봤던 그림과 유사함을 알 수 있습니다. 이 이분 그래프에서 자주 찾는 것이 있다면 그게 바로 이분 매칭인데요, 이분 매칭이란, 이분 그래프에서 최대한 많이 매칭할 수 있는 개수를 뜻합니다.
위의 그림은 주어진 이분 그래프 예시의 이분 매칭을 나타낸 그림이라고 할 수 있습니다. 이분 매칭을 구하는 알고리즘에 대한 설명은 위 링크를 통해 확인하실 수 있습니다. 저는 DFS를 통해 구현하였습니다.
이제, 이분 그래프며, 매칭이며 최소 버텍스 커버이며 하는 내용을 모두 종합해 쾨닉의 정리를 이해할 수 있습니다. 쾨닉의 정리란, 이분 그래프에서 이분 매칭은 그 그래프의 최소 버텍스 커버와 같다는 것입니다. 혹시, 위에서 최소 버텍스 커버를 설명할 때, 그럼 이걸 어떻게 코드로 구현할 수 있는지 생각해보셨나요? 아마 쉽지 않았을 겁니다. 쾨닉의 정리가 주는 이점은, 일반적인 그래프에서 최소 버텍스 커버를 구하는 것이 쉽지 않은데 이분 그래프만큼은 이분 매칭을 구함으로써 최소 버텍스 커버를 우회적으로 구할 수 있다는 점에 있는 것 같습니다.
그래서?
이렇게 장황한 이론들을 왜 늘어 놓았냐면, 이 컨닝 문제에서 각 자리를 정점으로, 그 자리에서 컨닝을 할 수 있는지의 여부를 간선으로 나타낸 그래프는 (1) 이분 그래프로 표현될 수 있고 (2) 최대한 많은 자리에 학생을 앉힌다는 것은 간선으로 연결되지 않는 정점들의 최대 갯수, 즉, 최대 독립 집합을 구하는 문제이기 때문입니다.
첫번째, 입력받은 자리들을 이분 그래프로 나타내는 것은 홀수열과 짝수열로 구분하는 것으로 쉽게 가능합니다. 왜냐하면, 홀수열끼리는 컨닝을 할 수 없고, 짝수열끼리도 컨닝을 할 수 없지만 홀수열과 짝수열은 서로 컨닝할 수 있는 자리가 존재하기 때문입니다.
위의 그림을 보면, 주황색 정점들과 파란색 정점들의 두 그룹으로 나눈다고 할 때, 이분 그래프로 표현할 수 있음을 쉽게 이해할 수 있습니다. 이 때, 각 그룹은 총 8개씩의 정점을 가지고 있게 되겠죠?
두번째, 이 이분 그래프에서 최대 독립 집합을 구하는 문제라고 했고, 최대 독립 집합은 그 그래프의 최소 버텍스 커버의 여집합이라고 했습니다. 이 때, 이분 그래프에서 최소 버텍스 커버의 정점 수는 쾨닉의 정리에 의해 이분 매칭의 개수와 동일합니다. 즉, 정리하자면 자리의 모양을 이분 그래프로 나타낸 뒤, 이분 매칭의 수(= 최소 버텍스 커버의 정점 수)를 구하고 존재하는 자릿 수에서 이분 매칭의 수를 빼서 구할 수 있습니다.
이 개념들을 코드로 구현하였습니다. 모두 제 방식대로 구현했기 때문에 이해가 잘 안갈 수 있습니다. 주석을 간단히 달아 두었으니 참고 바랍니다!!
import sys
import re
T = int(sys.stdin.readline())
results = []
def dfs(x):
global bimap
global matched
global visited
if visited[x]: return False
visited[x] = True
for y, link in enumerate(bimap[x]):
if link:
# bimap[x][y] = 0 # visited
if y not in matched or dfs(matched[y]):
matched[y] = x
return True
return False
for _ in range(T):
M, N = map(int, sys.stdin.readline().split())
x_start = 0
x_idx = 0
y_start = 0
y_idx = 0
max = 0
matched = {}
sit_cnt = 0
# 교실 모든 자리를 0으로 초기화
coord_map = []
for _ in range(M):
coord_map.append([0 for _ in range(N)])
X = {}
Y = {}
bimap = []
if N % 2 == 0:
for _ in range(int(N/2)*M): bimap.append([0 for _ in range(int(N/2)*M)])
else:
for _ in range((int(N/2)+1)*M): bimap.append([0 for _ in range(int(N/2)*M)])
# 입력받은 교실 의자의 정보를 이분 매칭(좌측 열을 X, 우측 열을 Y로 표현)의 형태로 분리함.
# X는 홀수열, Y는 짝수열로 둠. 각 열 내에서는 컨닝이 불가하므로
# 홀수열과 짝수열을 각각 이어 붙이면 이분 그래프를 그릴 수 있음.
# X, Y 모두 딕셔너리 이고, {(X 좌표, Y 좌표): (이분 매칭에서의 번호, 의자가 있는지 여부)} 형태로 만듦.
for x in range(M):
row = sys.stdin.readline().replace("\n", "")
turn = "X"
x_idx = x_start
y_idx = y_start
for y, value in enumerate(row):
if turn == "X":
if value == ".":
X[(x, y)] = (x_idx, 1)
sit_cnt += 1
else: X[(x, y)] = (x_idx, 0)
x_idx += M
turn = "Y"
else:
if value == ".":
Y[(x, y)] = (y_idx, 1)
sit_cnt += 1
else: Y[(x, y)] = (y_idx, 0)
y_idx += M
turn = "X"
x_start += 1
y_start += 1
# 각 좌표에 의자가 있는지 확인해 주는 맵 추가
for y, value in enumerate(row):
if value == ".": coord_map[x][y] = 1
# 홀수열(X)에 대해서만 루프를 돌림
for x, y in X:
item = X[(x, y)]
if not item[1]: continue
# 컨닝이 가능한 위치들
candidates = [(x-1, y-1), (x, y-1), (x+1, y-1), (x-1, y+1), (x, y+1), (x+1, y+1)]
for cx, cy in candidates:
# 컨닝이 가능한 위치들 중에서 의자가 있는 경우,
if 0 <= cx < M and 0 <= cy < N and coord_map[cx][cy]:
# 루프로 돌고 있는 좌표의 이분 그래프 X index와
# 컨닝이 가능한 자리들의 이분 그래프 Y index를 반환하고
bigraph_x = X[(x, y)][0]
bigraph_y = Y[(cx, cy)][0]
# 그 두 좌표를 이음.
bimap[bigraph_x][bigraph_y] = 1
# 이분 그래프에서의 최소 버텍스 커버를 구하기 위한 dfs를 돌림.
for i in range(len(X)):
visited = [False for _ in range(len(X))]
dfs(i)
result = sit_cnt - len(matched)
results.append(result)
for result in results:
sys.stdout.write(str(result)+'\n')
'Python > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘: python 3] #1018 - 체스판 다시 칠하기 (0) | 2020.01.15 |
|---|---|
| [백준 알고리즘: python 3] #1017 - 소수 쌍 (1) | 2020.01.14 |
| [백준 알고리즘: python 3] #1016 - 제곱 ㄴㄴ수 (2) | 2019.11.02 |
| [백준 알고리즘: python 3] #1015 - 수열 정렬 (0) | 2019.11.01 |
| [백준 알고리즘: python 3] #1013 - Contact (0) | 2019.09.12 |
