[백준/Java] #18808 스티커 붙이기

 

스티커 붙이기 (18808번)

사용 언어 : Java
레벨 : 골드3
📎 https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

 

❓ 접근

문제가 굉장히 긴데 열심히 읽어보니 문제 자체는 그렇게 어렵지 않았는데 구현을 어떻게 하느냐가 문제였다. 문제를 간단하게 요약하면

 

1. 왼쪽 위부터 스티커를 붙일 수 있는지 확인한다.

2. 전부 다 확인했을 때 붙이지 못하면 90도 회전한다.

3. 회전 후 1 ~ 2 과정 반복 (270도까지 회전)

4. 전체 스티커가 붙어있는 부분의 크기를 출력한다.

 

 

사실 이 과정 그대로 로직으로 구성하면 됐는데 나는 처음에 스티커를 붙이는 메서드와 스티커를 90도로 회전하는 함수로 나눠서 코드를 짜다가 스티커를 붙이는 메소드 안에서 모든 걸 구현하려고 하다 보니 for문이 계속해서 중첩되니까 짜는 나도 헷갈려서 왼쪽 위부터 스티커를 붙일 수 있는 확인하는 메서드, 실제로 붙이는 메서드를 따로 분리하기로 했다.

 

✏️ 풀이

 

public class BOJ18808 {
    static int[][] note, sticker;
    static int N, M, K, stickerN, stickerM, count, result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 세로의 길이
        M = Integer.parseInt(st.nextToken()); // 가로의 길이
        K = Integer.parseInt(st.nextToken()); // 스티커의 개수
        note = new int[N][M];
        for(int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            stickerN = Integer.parseInt(st.nextToken()); // 스티커의 세로 길이
            stickerM = Integer.parseInt(st.nextToken()); // 스티커의 가로 길이
            sticker = new int[stickerN][stickerM];
            // 입력받은 스티커 정보 배열에 저장
            // 스티커를 붙였을 때 스티커의 크기를 나중에 답에 더해야하기 때문에 count 초기화
            count = 0;
            for(int j = 0; j < stickerN; j++) {
                st = new StringTokenizer(br.readLine());
                for(int k = 0; k < stickerM; k++) {
                    sticker[j][k] = Integer.parseInt(st.nextToken());
                    if(sticker[j][k] == 1) count++;
                }
            }
            // 함수 실행
            noteCheck();
            // 스티커를 붙였을 때 정답에 count를 더해준다.
            result += count;
        }

        // 총 스티커의 크기 출력
        System.out.println(result);
    }
}

 

우선 스티커 배열 입력을 받으면서 1일 경우 즉, 스티커 부분일 경우 count를 증가시켜서 각 스티커에 대한 count를 갖고 있다가 함수 실행이 끝났을 때 스티커를 붙였으면 답에 count를 더해서 최종적으로 구하고자 하는 스티커 부분에 대한 크기를 담을 수 있도록 입력을 받았다.

 

static void noteCheck() {
        // 스티커를 붙이지 못할 경우 90도로 회전해야 하므로 최대 4번 실행
        for(int k = 0; k < 4; k++) {
            // 전체 크기에서 스티커의 크기만큼만 돌림
            for(int i = 0; i <= N - stickerN; i++) {
                for(int j = 0; j <= M - stickerM; j++) {
                    // 현재 좌표를 기준으로 스티커를 붙이기에 성공했을 때 리턴
                    if(sticking(i, j)) return;
                }
            }

            // 스티커를 붙이지 못했을 때 90도로 회전
            rotation90();
        }

        // 여기까지 왔는데도 붙이지 못했으면 답에 추가할 수 없으니까 count를 다시 0으로 초기화
        count = 0;
    }

 

note 배열(전체 모눈종이)을 왼쪽 위부터 확인하면서 현재 위치를 기준점으로 잡고 스티커를 붙일 수 있는지 확인하기 위해 sticking 함수에 현재 위치를 매개변수로 보내줬고, boolean 타입으로 true가 반환되면 스티커 붙이기를 성공했다는 뜻이니 밑에 함수를 실행하지 않고 바로 return 해주었다. 만약 2중 for문 (모든 위치 확인)이 끝났는데도 스티커를 붙이지 못했다면 90도로 회전하는 함수인 rotation90()을 실행해 주고 만약 4번 회전했는데도 붙이지 못했다면 답에 추가하지 못하니까 main에서 더하지 못하도록 count를 다시 0으로 초기화해주었다. 

 

// 스티커 붙이기 메소드
    static boolean sticking(int x, int y) {
        // 시작점을 기준점으로 잡고 스티커의 크기만큼 실행
        for(int i = 0; i < stickerN; i++) {
            for(int j = 0; j < stickerM; j++) {
                // 만약 스티커 부분도 1이고 노트북의 시작점을 기준으로 같은 부분이 1일땐 스티커를 붙일 수 없는 경우니까 false 리턴
                if(sticker[i][j] == 1 && note[i + x][j + y] == 1) return false;
            }
        }

        // 여기까지 왔을 경우 스티커를 붙일 수 있으니까 note 배열에 복사
        // 배열 자체를 복사하는 함수를 썼었는데 전에 붙였던 스티커 부분이 현재 붙이려는
        // 스티커 배열 그 자체를 복사하니까 0으로 바껴서 스티커를 붙이는 부분에만 1로 바꿔줌
        for(int i = 0; i < stickerN; i++) {
            for(int j = 0; j < stickerM; j++) {
                if(sticker[i][j] == 1) note[i + x][j + y] = 1;
            }
        }

        // 스티커 붙이기를 성공했으니 true 반환
        return true;
    }

 

실제로 스티커를 붙이는 함수로 들어오면 매개변수로 받은 현재 위치를 기준점으로 스티커의 크기만큼 실행하면서 만약 스티커 부분도 1이고, 노트북의 시작점을 기준으로 같은 부분이 1일 때는 스티커를 붙일 수 없는 경우니까 바로 false를 리턴해주고 for문이 전부 끝날 때까지 false를 반환하지 않으면 스티커를 붙일 수 있는 것이니까 note 배열에 복사하였다.

 

다만 복사하는 과정에서 처음에 배열을 그대로 복사하는 메서드를 사용했었는데 그렇게 하니까 전에 붙였던 스티커 부분이 0으로 바뀌는 상황이 생겨서 그냥 스티커 배열이 1일 경우에만 해당 부분을 1로 바꿔주었다.

 

static void rotation90() {
        // 90도 회전을 위한 스티커 배열 카피
        int[][] tmp = new int[stickerN][stickerM];
        for(int i = 0; i < stickerN; i++) {
            tmp[i] = Arrays.copyOf(sticker[i], sticker[i].length);
        }
        // 스티커의 크기가 바꼈으니까 복사한 배열의 가로 세로 값을 바꿔서 넣어줌
        stickerN = tmp[0].length;
        stickerM = tmp.length;

        // 스티커 배열을 회전한 크기로 다시 선언
        sticker = new int[stickerN][stickerM];
        for(int i = 0; i < stickerM; i++) {
            for(int j = 0; j < stickerN; j++) {
                // 회전하고 난 후의 i가 회전하기 전 j
                // 회전하고 난 후의 j가 회전하기 전 행 - 1 - i
                sticker[j][stickerM - 1 - i] = tmp[i][j];
            }
        }
    }

 

90도로 회전하는 함수에서는 임시배열을 만들어서 스티커 배열을 카피하고 전역변수로 선언해서 사용하고 있던 스티커의 가로 세로 크기가 변했으니까 임시배열의 가로 세로 값을 반대로 넣어주었다.

그리고 스티커 배열을 회전한 크기로 다시 선언하였는데 배열을 90도로 회전할 경우 회전하고 난 후의 i는 회전하기 전 j이며 회전하고 난 후의 i는 회전하기 전 행의 수 - 1 - i 이 규칙을 사용하여 배열을 회전시켜 주었다.

 

💡 전체 코드

 

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


public class BOJ18808 {
    static int[][] note, sticker;
    static int N, M, K, stickerN, stickerM, count, result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 세로의 길이
        M = Integer.parseInt(st.nextToken()); // 가로의 길이
        K = Integer.parseInt(st.nextToken()); // 스티커의 개수
        note = new int[N][M];
        for(int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            stickerN = Integer.parseInt(st.nextToken()); // 스티커의 세로 길이
            stickerM = Integer.parseInt(st.nextToken()); // 스티커의 가로 길이
            sticker = new int[stickerN][stickerM];
            // 입력받은 스티커 정보 배열에 저장
            // 스티커를 붙였을 때 스티커의 크기를 나중에 답에 더해야하기 때문에 count 초기화
            count = 0;
            for(int j = 0; j < stickerN; j++) {
                st = new StringTokenizer(br.readLine());
                for(int k = 0; k < stickerM; k++) {
                    sticker[j][k] = Integer.parseInt(st.nextToken());
                    if(sticker[j][k] == 1) count++;
                }
            }
            // 함수 실행
            noteCheck();
            // 스티커를 붙였을 때 정답에 count를 더해준다.
            result += count;
        }

        // 총 스티커의 크기 출력
        System.out.println(result);
    }

    static void noteCheck() {
        // 스티커를 붙이지 못할 경우 90도로 회전해야 하므로 최대 4번 실행
        for(int k = 0; k < 4; k++) {
            // 전체 크기에서 스티커의 크기만큼만 돌림
            for(int i = 0; i <= N - stickerN; i++) {
                for(int j = 0; j <= M - stickerM; j++) {
                    // 현재 좌표를 기준으로 스티커를 붙이기에 성공했을 때 리턴
                    if(sticking(i, j)) return;
                }
            }

            // 스티커를 붙이지 못했을 때 90도로 회전
            rotation90();
        }

        // 여기까지 왔는데도 붙이지 못했으면 답에 추가할 수 없으니까 count를 다시 0으로 초기화
        count = 0;
    }
    // 스티커 붙이기 메소드
    static boolean sticking(int x, int y) {
        // 시작점을 기준점으로 잡고 스티커의 크기만큼 실행
        for(int i = 0; i < stickerN; i++) {
            for(int j = 0; j < stickerM; j++) {
                // 만약 스티커 부분도 1이고 노트북의 시작점을 기준으로 같은 부분이 1일땐 스티커를 붙일 수 없는 경우니까 false 리턴
                if(sticker[i][j] == 1 && note[i + x][j + y] == 1) return false;
            }
        }

        // 여기까지 왔을 경우 스티커를 붙일 수 있으니까 note 배열에 복사
        // 배열 자체를 복사하는 함수를 썼었는데 전에 붙였던 스티커 부분이 현재 붙이려는
        // 스티커 배열 그 자체를 복사하니까 0으로 바껴서 스티커를 붙이는 부분에만 1로 바꿔줌
        for(int i = 0; i < stickerN; i++) {
            for(int j = 0; j < stickerM; j++) {
                if(sticker[i][j] == 1) note[i + x][j + y] = 1;
            }
        }

        // 스티커 붙이기를 성공했으니 true 반환
        return true;
    }
    // 90도 회전
    static void rotation90() {
        // 90도 회전을 위한 스티커 배열 카피
        int[][] tmp = new int[stickerN][stickerM];
        for(int i = 0; i < stickerN; i++) {
            tmp[i] = Arrays.copyOf(sticker[i], sticker[i].length);
        }
        // 스티커의 크기가 바꼈으니까 복사한 배열의 가로 세로 값을 바꿔서 넣어줌
        stickerN = tmp[0].length;
        stickerM = tmp.length;

        // 스티커 배열을 회전한 크기로 다시 선언
        sticker = new int[stickerN][stickerM];
        for(int i = 0; i < stickerM; i++) {
            for(int j = 0; j < stickerN; j++) {
                // 회전하고 난 후의 i가 회전하기 전 j
                // 회전하고 난 후의 j가 회전하기 전 행 - 1 - i
                sticker[j][stickerM - 1 - i] = tmp[i][j];
            }
        }
    }
}

 

코드를 짜는데 시행착오는 별로 없었으나.. 코드가 길어지면서 시간초과 날 것 같다는 생각에 어떻게든 다른 방법을 사용해보려고 했다가 오히려 시간을 더 버린 것 같다. 일단 이렇게 풀어보자 하고 백준에 제출을 해봤는데 다행히 시간초과는 나지 않아서 지저분했던 코드만 조금 수정하기만 했다. 

 

 

시뮬레이션 문제를 접한 지 얼마 안 돼서 아직 너무 어렵지만 생각보다 문제들이 재미있는 것 같다! 내가 이렇게 긴 코드를 짜면서 풀었다는 게 신기하기도 하고 ㅎ.ㅎ 스터디에서도 다들 으쌰으쌰 하면서 코드리뷰하니까 더 재밌고 다들 실력이 느는 게 보이는 것 같다 🤗 앞으로도 지치지 않고 파이팅ㅇ하길!