‘W’는 흰색, ‘B’는 파란색, ‘R’은 빨간색을 의미한다. ‘W’, ‘B’, ‘R’외의 다른 문자는 입력되지 않는다.
첫 번째 예제이다. 왼쪽에 있는 그림이 입력이다. 중간에 있는 그림에 X가 적힌 칸들을 새롭게 색칠하여 오른쪽에 있는 그림과 같은 깃발을 만들면 최적이다.
이렇게 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여라.
조합으로 접근할 수 있다. 예를 들어 4줄이 주어질 때 1,2,3 중 숫자 1,2 2개를 선택하면 1줄은 흰색, 1줄은 파랑색, 나머지 2줄은 빨간색으로 채울 수 있다. 이러한 경우의 수를 모두 탐색 후 최소값을 구하면 되기 때문이다.
러시아 깃발은 3색이기 때문에 아무리 많은 줄이 주어져도 nC2 의 경우의 수만 탐색하면 된다.
조합의 경우의 수를 모두 탐색하는 DFS 알고리즘을 작성한다.
def dfs(L,s):
global answer
if L == 2 :
result = count(res[0],res[1])
if answer > result:
answer = result
return
else:
for i in range(s,len(nums)):
res[L] = nums[i]
dfs(L+1,i+1)
def color(i, c):
result = 0
for j in range(M):
if flags[i][j] != c:
result += 1
return result
def count(a,b):
result = 0
for i in range(0,N):
if i < a :
result += color(i, 'W')
elif a <= i < b:
result += color(i, 'B')
else :
result += color(i,'R')
return result
def color(i, c):
result = 0
for j in range(M):
if flags[i][j] != c:
result += 1
return result
def count(a,b):
result = 0
for i in range(0,N):
if i < a :
result += color(i, 'W')
elif a <= i < b:
result += color(i, 'B')
else :
result += color(i,'R')
return result
def dfs(L,s):
global answer
if L == 2 :
result = count(res[0],res[1])
if answer > result:
answer = result
return
else :
for i in range(s,len(nums)):
res[L] = nums[i]
dfs(L+1,i+1)
T = int(input())
for t in range(1, 1+T):
N, M = map(int, input().split())
flags = [list(input()) for _ in range(N)]
nums = [i for i in range(N) if i]
res = [None,None]
answer = 999999999999
dfs(0,0)
print(f'#{t} {answer}')