러시아 국기같은 깃발 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 4613

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

2016년은 삼성전자가 러시아 현지법인을 설립한지 20주년이 된 해이다. 이를 기념해서 당신은 러시아 국기를 만들기로 했다. 먼저 창고에서 오래된 깃발을 꺼내왔다. 이 깃발은 N행 M열로 나뉘어 있고, 각 칸은 흰색, 파란색, 빨간색 중 하나로 칠해져 있다. 당신은 몇 개의 칸에 있는 색을 다시 칠해서 이 깃발을 러시아 국기처럼 만들려고 한다. 다음의 조건을 만족해야 한다. 위에서 몇 줄(한 줄 이상)은 모두 흰색으로 칠해져 있어야 한다. 다음 몇 줄(한 줄 이상)은 모두 파란색으로 칠해져 있어야 한다. 나머지 줄(한 줄 이상)은 모두 빨간색으로 칠해져 있어야 한다. 이렇게 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여라. 첫 번째 예제이다. 왼쪽에 있는 그림이 입력이다. 중간에 있는 그림에 X가 적힌 칸들을 새롭게 색칠하여 오른쪽에 있는 그림과 같은 깃발을 만들면 최적이다.

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 N,M(3≤N,M≤50)이 공백으로 구분되어 주어진다. 다음 N개의 줄에는 M개의 문자로 이루어진 문자열이 주어진다. i번 째 줄의 j번째 문자는 깃발에서 i번째 행 j번째 열인 칸의 색을 의미한다. ‘W’는 흰색, ‘B’는 파란색, ‘R’은 빨간색을 의미한다. ‘W’, ‘B’, ‘R’외의 다른 문자는 입력되지 않는다.

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여 T 줄에 걸쳐서 출력한다.

예시

입력	출력
2 4 5 WRWRW BWRWB WRWRW RWBWR 6 14 WWWWWWWWWWWWWW WWRRWWBBBBBBWW WRRRWWWBWWWWRB WWBWBWWWBWRRRR WBWBBWWWBBWRRW WWWWWWWWWWWWWW	#1 11 #2 44

---

2. 문제풀이

dfs를 이용하여 모든 경우의 수를 탐색하였다. dfs하면서 바꿔야 하는 개수를 카운팅하고 저장된거보다 카운팅횟수가 더커지면 더이상 진행이 되지 않도록 가지치기를 하였다. 계산을 할때 첫줄과 마지막 줄은 하지 않았는데 제일 첫줄은 흰색으로 고정이고 제일 마지막줄은 빨간색으로 고정이기 때문에 재귀의 횟수를 줄이기 위해 이렇게 했다. 마지막에 따로 제일 윗줄과 아랫줄을 카운팅하고 값을 리턴하였다.

---

3. 소스코드

#D4 4613 러시아 국기 같은 깃발
targets = ['W', 'B', 'R']
 
def dfs(idx, color, _sum):
    global result
    #가치지기
    if result <= _sum : return
    #결과 더하기
    if idx >= N-1: 
        result = _sum
        return
    #다음색상까지, 넘어온게 흰색이라면  흰색, 파랑만
    #인덱스때문에 최댓값은 3으로 설정
    for i in range(color, min(3, color+2)):
        temp = 0
        #마지막줄까지 왔는데 컬러가 흰색이라면 다음으로 넘어가기
        if idx >= N-2 and i == 0: continue
        for j in Flag[idx]:
            #색상이 다른것들 카운트
            if j != targets[i]: temp += 1
        dfs(idx+1, i, _sum + temp)
 
#제일 윗줄과 아랫줄 체크하기
def init():
    global result
    for i in Flag[0]:
        if i != 'W': result += 1
    for i in Flag[N-1]:
        if i != 'R': result += 1
 
for t in range(1, int(input()) + 1):
    #입력받기
    N, M = map(int, input().split())
    Flag = [list(input()) for _ in range(N)]
    #최종 결과값
    result = 987654
    #갯수 체크하기
    dfs(1, 0, 0)
    #제일 위와 아래줄 체크하기
    init()
    print('#{} {}'.format(t, result))