[SWEA] 4613. 러시아 국기 같은 깃발 D4 - 조합

[SWEA] 4613. 러시아 국기 같은 깃발 D4 - Simulation

제출일 : 2019-11-16

문제 풀이 시간 : 20M

난이도 : ★★☆

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj

input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N,M(3≤N,M≤50)이 공백으로 구분되어 주어진다.

다음 N개의 줄에는 M개의 문자로 이루어진 문자열이 주어진다. i번 째 줄의 j번째 문자는 깃발에서 i번째 행 j번째 열인 칸의 색을 의미한다.

‘W’는 흰색, ‘B’는 파란색, ‘R’은 빨간색을 의미한다. ‘W’, ‘B’, ‘R’외의 다른 문자는 입력되지 않는다.

Output

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

Example

input

2
4 5
WRWRW
BWRWB
WRWRW
RWBWR
6 14
WWWWWWWWWWWWWW
WWRRWWBBBBBBWW
WRRRWWWBWWWWRB
WWBWBWWWBWRRRR
WBWBBWWWBBWRRW
WWWWWWWWWWWWWW

output

#1 11
#2 44

Solution & Inpression

가장 윗줄(0번)과 가장 아랫줄(N-1번)은 흰색과 빨간색으로 칠해져야 한다.

따라서 0~N-2까지의 수 중에서 2개의 수를 조합을 이용하여 뽑았는데 첫번째 숫자는 W로 칠해져야 하는 행의 숫자고 두번째 숫자는 B로 칠해져야 하는 행의 숫자이다.

이제 분할하여 색을 칠해줘야하는 경우를 세어 최소값을 구하면 된다.

Code

언어 : JAVA

메모리 : 28,928 kb

실행시간 : 175 ms

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {
    static int N, M;
    static char[][] map;
    static int ans;
    static int[] match;
    static boolean[] visit;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            M = sc.nextInt();
            map = new char[N][M];
            for (int i = 0; i < N; i++) {
                String str = sc.next();
                for (int j = 0; j < M; j++) {
                    map[i][j] = str.charAt(j);
                }
            }
            ans = Integer.MAX_VALUE;
            match = new int[2];
            visit = new boolean[N - 1];
            get(0, 0);

            System.out.println("#" + tc + " " + ans);
        }
    }

    private static void get(int start, int depth) {
        if (depth == 2) {
            solve();
            return;
        }
        for (int i = start; i < N - 1; i++) {
            if (!visit[i]) {
                visit[i] = true;
                match[depth] = i;
                get(i, depth + 1);
                visit[i] = false;
            }
        }

    }

    private static void solve() {
        int cnt = 0;
        // W
        for (int i = 0; i <= match[0]; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 'W')
                    cnt++;
            }
        }
        // B
        for (int i = match[0] + 1; i <= match[1]; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 'B')
                    cnt++;
            }
        }
        // R
        for (int i = match[1] + 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 'R')
                    cnt++;
            }
        }

        if (ans > cnt)
            ans = cnt;
    }
}