[BOJ - JAVA] 18808 - 스티커 붙이기 (브루트 포스)

# 주소

https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;

class Main {
    static int n,m,k,a,b;
    static int[][] arr;
    static int[][] ans;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        k = scan.nextInt();
        arr = new int[n][m];
        for(int i = 0; i < k; i++) {
            a = scan.nextInt();
            b = scan.nextInt();
            ans = new int[10][10];
            for(int j = 0; j < a; j++){
                for(int t = 0; t < b; t++){
                    ans[j][t] = scan.nextInt();
                }
            }
            dfs();
        }
        int cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cnt += arr[i][j];
            }
        }
        System.out.println(cnt);
    }
    static void dfs(){
        for(int i = 0; i < 4; i++){
            boolean flag = false;
            for(int nx = 0; nx <= n - a; nx++){
                if(flag)
                    break;
                for(int ny = 0; ny <= m - b; ny++){
                    if(check(nx,ny)){
                        flag = true;
                        break;
                    }
                }
            }
            if(flag)
                break;
            rotate();
        }
    }
    static boolean check(int x, int y){
        for(int i = 0; i < a; i++){
            for(int j = 0; j < b; j++){
                if(arr[x + i][y + j] == 1 && ans[i][j] == 1)
                    return false;
            }
        }
        for(int i = 0; i < a; i++){
            for(int j = 0; j < b; j++){
                if(ans[i][j] == 1){
                    arr[x + i][y + j] = 1;
                }
            }
        }
        return true;
    }
    static void rotate(){
        int[][] temp = new int[12][12];
        for(int i = 0; i < a; i++){
            if (b >= 0) System.arraycopy(ans[i], 0, temp[i], 0, b);
        }
        for(int i = 0; i < b; i++){
            for(int j = 0; j < a; j++){
                ans[i][j] = temp[a - 1 - j][i];
            }
        }
        int t = a;
        a = b;
        b = t;
    }
}

arr의 크기를 n x m로 선언합니다.

입력문으로 n,m,k를 입력받겠습니다.

n은 행, m은 열, k는 스티커의 개수를 의미합니다.

그러므로 첫 번째 for문으로 k개의 스티커를 입력받겠습니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
k = scan.nextInt();
arr = new int[n][m];

그리고 a와 b를 입력받습니다.

for(int i = 0; i < k; i++) {
    a = scan.nextInt();
    b = scan.nextInt();
    ans = new int[10][10];
    for(int j = 0; j < a; j++){
        for(int t = 0; t < b; t++){
            ans[j][t] = scan.nextInt();
        }
    }
    dfs();
}

a와 b를 입력받고 ans의 크기를 10 x 10로 지정합니다.

그리고 2중 for문으로 ans를 입력받습니다.

스티커의 위치값을 담은 배열이 ans입니다.

이 ans를 이용하여 arr에 붙이고 겹치는 부분이 있으면 break하여 탐색을 포기할 것입니다.

그리고 dfs를 실행합니다.

static void dfs(){
    for(int i = 0; i < 4; i++){
        boolean flag = false;
        for(int nx = 0; nx <= n - a; nx++){
            if(flag)
                break;
            for(int ny = 0; ny <= m - b; ny++){
                if(check(nx,ny)){
                    flag = true;
                    break;
                }
            }
        }
        if(flag)
            break;
        rotate();
    }
}

dfs의 구조는 다음과 같습니다.

첫 번째 for문에서는 90도씩 회전시키기 위해 4방향을 loop합니다.

이 때 flag = false로 초기화하고 만약 flag가 참일 때마다 break시켜줄거에요.

두 번째 for문과 세 번째 for문에서 int nx = 0과 int ny = 0에서부터 시작하여 각각 n-a와 m-b까지 탐색할 것입니다.

그리고 check(nx,ny)가 true이면 flag도 true로 바꾸고 break를 걸꺼에요.

이 check()함수는

static boolean check(int x, int y){
    for(int i = 0; i < a; i++){
        for(int j = 0; j < b; j++){
            if(arr[x + i][y + j] == 1 && ans[i][j] == 1)
                return false;
        }
    }
    for(int i = 0; i < a; i++){
        for(int j = 0; j < b; j++){
            if(ans[i][j] == 1){
                arr[x + i][y + j] = 1;
            }
        }
    }
    return true;
}

이렇게 생겼습니다.

이중for문을 이용해서 a행 b열까지 탐색할건데, 만약 arr[x + i][y + j]가 1이고 ans[i][j]도 1이면(탐색한 적이 있으면) return으로 false를 내보낼 것이니다.

그리고 모두 탐색한적이 없다면 다시 이중 for문을 이용해, arr[x+i][j+j]를 1로 바꿀 것입니다.

그 말은 스티커를 arr에 크기만큼 붙였다는 이야기에요.

더 나아가서 이걸 붙이는데 성공했으면 true를 return하여 flag도 true로 바꾸고 break할 것입니다.

자 이랬는데 flag와 check()가 모두 false여서 스티커를 못 붙힌다고 생각해봅시다.

그렇다면 회전을 시켜야겠죠?

이에 rotate()함수를 실행합니다.

static void rotate(){
        int[][] temp = new int[12][12];
        for(int i = 0; i < a; i++){
            if (b >= 0) System.arraycopy(ans[i], 0, temp[i], 0, b);
        }
        for(int i = 0; i < b; i++){
            for(int j = 0; j < a; j++){
                ans[i][j] = temp[a - 1 - j][i];
            }
        }
        int t = a;
        a = b;
        b = t;
    }
}

스티커를 회전하는 것이기 때문에 배열의 전체 값을 바꾸기 위해선 필연적으로 temp배열이 필요합니다.

temp배열의 크기를 10x10으로 선언합니다.

그리고 ans의 모든 배열 값을 temp로 옮깁니다.

이후 배열을 뒤집을건데, 한 번 뒤집을 때마다 90도씩 시계방향으로 뒤집을 것입니다.

그렇게 된다면 4 x 3이었던 배열은 3 x 4가 될 것이겠지요.

그리고 4 x 3의 1열의 값들은 3 x 4의 1행으로 이동한다고 해봅시다.

그러면 ans의 1행에는 temp의 1열이 새로 들어가기 때문에  ans[i][j]는 temp[~][i]가 되겠죠.

temp의 1열이 ans의 1행에 들어간다는 뜻입니다.

그리고 이건 외우는걸 장려하는데.. arr[i][j] 에서 i행에는 temp[a - 1 - j]가 들어가야 회전이 됩니다.

이게 머리는 이해하는데 '왜 그래요?' 라고 물으시면 머릿속으로 그려보시는걸 추천드립니다.

자 그리고 a와 b를 swap할 것인데, 우리 컴공에서 제일 처음 C배울 때 숫자 swap에 대해 배웁니다.

그 때 자주 쓰는 방법이 임시 변수 temp를 활용하는 것인데요.

아까 temp 배열을 선언해서 ans를 옮겨담았듯이 이번에는 회전할 때마다 a와 b를 서로 바꾸어주어야 하기 때문에 

t = a;

a = b;

b = t;로 swap을 하는 것입니다.

이렇게 rotate()함수가 종료되면 dfs()도 end되고 모든 탐색은 끝납니다.

cnt = 0으로 선언하여 arr값이 1인 지점만 cnt++해주고 cnt를 출력하면 그것이 정답이 되겠습니다.

감사합니다.