BOJ 18808 스티커 붙이기 [Java]

BOJ 18808 스티커 붙이기

1. 문제 링크

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

2. 문제 해설

구현 문제이다. 문제를 해결하기위해 구현해야하는 기능은 2개이다.

1. 스티커를 붙일 수 있으면 스티커를 붙이기
2. 스티커를 회전한다.

1번 기능을 구현하기 위해 2가지 메서드를 만들었다. 스티커를 노트북에 붙일 수 있는지 확인하는 isPossible 메서드와 스티커를 노트북에 붙이는 attach 메서드이다. isPossible 메서드는 매개변수로 스티커를 붙이는 노트북의 맨 왼쪽 상단 위치를 받는다. 노트북의 격자에 스티커가 이미 붙어있는 상황에서 스티커를 붙여야 할 때만 스티커를 붙이지 못하므로 false를 리턴해주고 나머지 상황에서는 true를 리턴해준다.
attach 메서드는 isPossible 메서드가 true일 때만 실행시켜줄 메서드이다. isPossible 메서드와 동일하게 스티커를 붙이는 노트북의 시작 격자 위치를 매개 변수로 받고 노트북에 스티커를 붙인다.

2번 기능 스티커를 회전하는 부분이 까다로웠다. 일단 회전하기 전의 기존 스티커 모양을 똑같이 저장할 임시 배열 tmp에 스티커를 담아준다.
그 후 106~110번째 줄의 코드를 작성하기가 힘들었는데, 스티커를 90도 회전시킨 모양과 tmp에 담겨있는 모양을 그려서 비교해보면서 규칙을 찾을 수 있었다. 이렇게 스티커 배열의 값만 회전시켜주고 r과 c의 값을 서로 바꿔주지 않으면 스티커를 회전시킨 것이 아니다. r과 c의 값도 바꿔주어야 최종적으로 스티커를 회전시킨 것이다.

위 메서드들을 이용해서 스티커를 붙이는 과정을 구현한 과정을 설명해보겠다.
스티커를 붙일 수 있으면 붙이고, 현재 방향에서 붙일 수 없으면 회전을 하면 된다. 동서남북을 다 확인해서 못 붙이면 붙이지 않는다.
34~56줄 코드의 내용이다. 일단 스티커가 붙었는지 안 붙었는지를 확인할 isAttach 변수를 만들어줬다. 스티커를 붙였으면 회전시킬 필요가 없기때문이다. 스티커를 붙일 수 있는 노트북의 격자 범위를 돌면서 isPossible 메서드가 true이면 attach 메서드를 이용해 스티커를 붙여주고 isAttach를 true로 바꿔준 후 반복문을 탈출한다. 지금 보고 있는 방향에서 스티커를 붙일 수 없으면 스티커를 회전시켜준다.

위 과정을 다 거친 후 노트북 배열을 확인하여 값이 1인 원소의 갯수를 세면 된다.

3. 코드 보기

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int n, m, k;
    static int r, c;
    static int[][] notebook;
    static int[][] sticker;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        notebook = new int[n][m];

        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            sticker = new int[10][10];

            for (int i = 0; i < r; i++) {
                st = new StringTokenizer(br.readLine());

                for (int j = 0; j < c; j++) {
                    sticker[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int dir = 0; dir < 4; dir++) {
                boolean isAttach = false;

                for (int i = 0; i <= n - r; i++) {
                    if (isAttach) {
                        break;
                    }

                    for (int j = 0; j <= m - c; j++) {
                        if (isPossible(i, j)) {
                            attach(i, j);
                            isAttach = true;
                            break;
                        }
                    }
                }

                if (isAttach) {
                    break;
                }

                rotate();
            }
        }

        int cnt = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (notebook[i][j] == 1) {
                    cnt++;
                }
            }
        }

        bw.write(Integer.toString(cnt));
        br.close();
        bw.flush();
        bw.close();
    }

    static boolean isPossible(int x, int y) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (notebook[x + i][y + j] == 1 && sticker[i][j] == 1) {
                    return false;
                }
            }
        }

        return true;
    }

    static void attach(int x, int y) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (sticker[i][j] == 1) {
                    notebook[x + i][y + j] = 1;
                }
            }
        }
    }

    static void rotate() {
        int[][] tmp = new int[10][10];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                tmp[i][j] = sticker[i][j];
            }
        }

        for (int i = 0; i < c; i++) {
            for (int j = 0; j < r; j++) {
                sticker[i][j] = tmp[r - 1 - j][i];
            }
        }

        int temp = r;
        r = c;
        c = temp;
    }
}