백준: 18808번 (스티커 붙이기) [JAVA]

문제 링크

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

18808번: 스티커 붙이기

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어지는 패널의 사이즈와 스티커들의 정보를 저장
2. 문제에서 요구하는 방식대로 순서대로 스티커를 회전, 이동하며 붙일 수 있는 패널에 부착
3. 스티커를 붙이며 해당 스티커가 차지하는 칸을 반환하며 이를 모두 답에 누적 후 반환

 문제 해결을 위해 특정 알고리즘을 필요로 하기 보다는, 문제 요구하는 바를 구대로 구현할 수 있는 지를 보는 구현 문제에 가깝다. 문제에서 스티커를 붙이는 과정이 회전을 안한 상태에서 패널의 왼쪽 위부터 오른쪽으로 이동하며 스티커를 붙일 수 있는 지 체크하고, 만약 불가능하면 이후 90도씩 회전을 해가며 탐색을 진행하기 때문에 문제에서 요구하는 대로 스티커를 0도, 90도, 180도, 270도 회전하고 2중 for문으로 패널의 전체부분에서 탐색이 가능한 지를 확인하도록 함수를 구현한다. 이후 해당 스티커를 붙일 수 있는 지가 확인되면 패널에 스티커를 옮겨 붙이고, 이후 스티커가 붙은 칸의 개수를 추가적으로 반환한다. 이렇게 주어진 스티커에 대해 모두 반복하며 그 반환 값을 누적하면, 해당 누적값이 문제에서 요구하는 스티커가 붙은 칸의 개수가 된다.

 

public class Main {
    static int N, M, K;
    static int[][] panel, stickerInfor;
    static int[][][] stickers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;

        //N, M, K 초기화
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        panel = new int[N][M];
        stickers = new int[K][10][10];
        stickerInfor = new int[K][2];

        for (int i = 0; i < K; i++) {//스티커 & 스티커 정보 저장
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            stickerInfor[i][0] = r;
            stickerInfor[i][1] = c;

            for (int j = 0; j < r; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < c; k++) {
                    stickers[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }

        for (int i = 0; i < K; i++) {//각 스티커 함수 호출
            answer += attach(i);
        }

        System.out.println(answer);
    }

    static int attach(int stickerNum) {//패널에 스티커 붙이기
        int[][] rotateResult = new int[10][10];
        int r = stickerInfor[stickerNum][0], c = stickerInfor[stickerNum][1]
                , rotateR, rotateC, count = 0;

        for (int i = 0; i < 4; i++) {//회전 순서 대로 진행
            if (i == 0) {//제자리
                rotateR = r;
                rotateC = c;

                for (int j = 0; j < r; j++) {
                    for (int k = 0; k < c; k++) {
                        rotateResult[j][k] = stickers[stickerNum][j][k];
                    }
                }
            } else if (i == 1) {//90도
                rotateR = c;
                rotateC = r;

                for (int j = 0; j < r; j++) {
                    for (int k = 0; k < c; k++) {
                        rotateResult[k][r - 1 - j] = stickers[stickerNum][j][k];
                    }
                }
            } else if (i == 2) {//180도
                rotateR = r;
                rotateC = c;

                for (int j = 0; j < r; j++) {
                    for (int k = 0; k < c; k++) {
                        rotateResult[r - 1 - j][c - 1 - k] = stickers[stickerNum][j][k];
                    }
                }
            } else {//270도
                rotateR = c;
                rotateC = r;

                for (int j = 0; j < r; j++) {
                    for (int k = 0; k < c; k++) {
                        rotateResult[c - 1 - k][j] = stickers[stickerNum][j][k];
                    }
                }
            }

            for (int j = 0; j <= N - rotateR; j++) {//스티커를 붙일 수 있는 지 각 위치 확인
                for (int k = 0; k <= M - rotateC; k++) {
                    boolean matchResult = true;

                    for (int l = 0; l < rotateR; l++) {
                        for (int m = 0; m < rotateC; m++) {
                            if (panel[j + l][k + m] == 1 && rotateResult[l][m] == 1) {
                                matchResult = false;
                                break;
                            }
                        }

                        if (!matchResult) {
                            break;
                        }
                    }

                    if (matchResult) {//붙일 수 있다면 패널 최신화 후 붙인 칸만큼 반환
                        for (int l = 0; l < rotateR; l++) {
                            for (int m = 0; m < rotateC; m++) {
                                if (rotateResult[l][m] == 1) {
                                    ++count;
                                    panel[j + l][k + m] = rotateResult[l][m];
                                }
                            }
                        }

                        return count;
                    }
                }
            }
        }
        return count;
    }
}

결과