[23562] ㄷ 만들기

Rae-eun Yang·2022년 9월 15일

Java baekjoon 구현 백준

백준

목록 보기

9/14

문제

2021년, 냅다 ㄷ 만들기는 한국인의 기본 소양이 되었다. 우리는 앞에 놓여있는 $n \times m$ 모눈종이에 냅다 ㄷ을 그리려 한다.

ㄷ 모양은 $k \times k$ 정사각형 7개를 붙인 형태로 정의한다. 다음은 각각 $k=1, k=2$ 일 때의 ㄷ 모양이다.

ㄷ 모양이 아닌 것의 예는 다음과 같다.

모눈종이의 일부 칸에는 이미 검은색이 칠해져 있다. 흰색 칸을 검은색으로 칠하는 데 드는 비용은 $a$ , 검은색 칸을 지워서 흰색 칸으로 만드는 데 드는 비용은 $b$ 다. 검은색 칸들이 ㄷ 모양을 이룰 수 있도록 하기 위해 드는 최소 비용을 구하는 프로그램을 작성하자.

ㄷ 모양의 위치와 크기에는 제한이 없지만, 뒤집거나 돌릴 수는 없으며, 모눈종이를 벗어나도 안 된다. 또한, 모든 검은색 칸은 ㄷ 모양에 포함되어야 하고, ㄷ 모양에 포함되지 않는 칸은 모두 흰색이어야 한다.

입력

첫 번째 줄에 모눈종이의 크기 $n, m$ 이 주어진다.

두 번째 줄에 칸의 색깔을 바꾸는 데 드는 비용 $a,b$ 가 주어진다.

다음 $n$ 개의 줄에 길이 $m$ 인 문자열이 주어진다. #은 검은색으로 칠해진 칸, .은 흰색 칸을 의미한다.

출력

첫 번째 줄에 ㄷ 모양을 만들 수 있는 최소 비용을 출력한다.

제한

$3 \le n,m \le 20$
$1 \le a,b \le 1000$

예제 입력 1

3 3
2 5
#.#
.#.
#.#

예제 출력 1

예제 입력 2

6 7
10 15
.#####.
.#####.
.#.....
.#.....
.#####.
.#####.

예제 출력 2

예제 입력 3

8 8
1000 1
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#

예제 출력 3

예제 입력 4

8 8
1 1000
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#

예제 출력 4

풀이 코드 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
		
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][m];
        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < m; j++) {
                // 검은색(#)은 1로, 하얀색(.)은 0으로 저장
                if(s.charAt(j) == '#') {
                    arr[i][j] = 1;
                } else if(s.charAt(j) == '.') {
                    arr[i][j] = 0;
                }
            }
        }

        // 계산 부분
        int whiteToBlack = 0;
        int blackToWhite = 0;
        int min = Integer.MAX_VALUE;
        int k = 1;

        // ㄷ의 범위를 정의하는 i(세로)와 j(가로)
        while(n >= (k * 3) && m >= (k * 3)) {
            for (int i = 0; i <= n - (k * 3); i++) {
                for (int j = 0; j <= m - (k * 3); j++) {
                    whiteToBlack = 0;
                    blackToWhite = 0;
                    // 검정색 -> 하얀색 || 하얀색 -> 검정색 찾기
                    for (int p = 0; p < n; p++) {
                        for (int q = 0; q < m; q++) {
                            // ㅁ 범위 내 - ㅁ의 범위 중에서 ㄷ의 범위가 아닌 것 = ㄷ의 범위
                            // ㄷ 범위 내 하얀색 -> 검은색
                            if ((j <= q) && (q < j + (k * 3)) && (i <= p) && (p < i + (k * 3)) && !((j + k <= q) && (q < j + (k * 3)) && (i + k <= p) && (p < i + (k * 2)))) {
                                if (arr[p][q] == 0) whiteToBlack++;
                            } // ㄷ 범위 외 검은색 -> 하얀색
                            else {
                                if (arr[p][q] == 1) blackToWhite++;
                            }
                        }
                    }
                    min = min < (whiteToBlack * a) + (blackToWhite * b) ? min : (whiteToBlack * a) + (blackToWhite * b);
                }
            }
            k++;
        }

        System.out.println(min);

    }

}

int arr[][] : 모눈종이의 상태를 나타내는 2차원 배열 (검정 = 1, 흰색 = 0)
whiteToBlack : 하얀색 -> 검정색으로 바꿔야 하는 수
blackToWhite : 검정색 -> 하얀색으로 바꿔야 하는 수