[백준/C++] 18808 - 스티커 붙이기

풀이 시간: 2h08m57s01

시간 복잡도: O(NMRC)

공간 복잡도: O(NM + RC)

문제

입력

첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 ≤ M ≤ 40), 그리고 스티커의 개수 K(1 ≤ K ≤ 100)이 한 칸의 빈칸을 사이에 두고 주어진다.

그 다음 줄부터는 K개의 스티커들에 대한 정보가 주어진다. 각 스티커는 아래와 같은 형식으로 주어진다.

먼저 i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 Ri(1 ≤ Ri ≤ 10)와 Ci(1 ≤ Ci ≤ 10)가 한 칸의 빈칸을 사이에 두고 주어진다.

다음 Ri개의 줄에는 각 줄마다 모눈종이의 각 행을 나타내는 Ci개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1이다. 0은 스티커가 붙지 않은 칸을, 1은 스티커가 붙은 칸을 의미한다.

문제에서 설명한 것과 같이 스티커는 모두 올바른 모눈종이에 인쇄되어 있다. 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

출력

첫째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력한다.

문제 풀이

일단 문제의 설명이 친절하게 나와있어서 따로 정리하진 않았고 문제에 나와있는 방식대로 코드를 구현해보았다.

초기 코드

#include <iostream>
#include <vector>
using namespace std;
int N, M, K, R, C;
bool check = false;
vector<vector<int>> arr, temp;

void stick() {
    // 전체 위치 순회하여 붙일 수 있는 공간 찾아 붙이기
    for (int i = 0; i <= N - R; ++i) { 
        for (int j = 0; j <= M - C; ++j) {
            bool flag = true;
            for (int r = 0; r < R; ++r)
                for (int c = 0; c < C; ++c) {
                    if (temp[r][c] == 1 && arr[r + i][c + j] == 1) 
                        { flag = false; break; } // 이미 스티커가 붙여있을 경우 종료
                }
            if (flag) { // 해당 스티커 붙이기
                check = true;
                for (int r = 0; r < R; ++r)
                    for (int c = 0; c < C; ++c)
                        if (temp[r][c] == 1)
                            arr[r][c] = temp[r][c];
            }
        }
    }
}

void rotate() {
    for (int i = 0; i < 4; ++i) { // 0도, 90도, 180도, 270도
        stick();
        if (check) break; // 스티커 붙었을 경우 회전 종료
        int T = R; R = C; C = T; // R <-> C
        vector<vector<int>> rotated(R, vector<int>(C));
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
                rotated[i][C - j - 1] = temp[j][i];
        temp = rotated;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    arr = vector<vector<int>>(N, vector<int>(M, 0));
    for (int i = 0; i < K; ++i) {
        cin >> R >> C;
        temp = vector<vector<int>>(R, vector<int>(C, 0));
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                cin >> temp[r][c];
        // 똑바로 해도, 90도 회전해도 스티커가 노트북보다 클 경우 스티커 버림
        if ((R > N || C > M) && (R > M || C > N)) continue;
        check = false; // 스티커 부착 여부
        rotate(); // 스티커 회전
    }
    int cnt = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            if (arr[i][j] == 1) cnt++;
    cout << cnt;
    return 0;
}

결괏값이 전부 다르게 나와서 하나씩 출력해보니, 예제 1번 출력이 다음과 같이 나왔다.

1 1 1 0 
1 1 1 0 
1 1 1 0 
1 1 0 0 
0 1 0 0

stick() 함수에서 문제가 있는 것 같았다. 보아하니 전체 위치를 순회하면서 탐색은 했는데, 막상 스티커를 붙일 때 그 위치부터 시작하여 붙여주지 않아서 발생한 문제였다.

// 기존 오류 코드
void stick() {
    for (int i = 0; i <= N - R; ++i) { 
        for (int j = 0; j <= M - C; ++j) {
            bool flag = true;
            for (int r = 0; r < R; ++r)
                for (int c = 0; c < C; ++c) {
                    if (temp[r][c] == 1 && arr[r + i][c + j] == 1) // i, j 만큼 이동한 위치에서 탐색
                        { flag = false; break; }
                }
            if (flag) {
                check = true;
                for (int r = 0; r < R; ++r)
                    for (int c = 0; c < C; ++c)
                        if (temp[r][c] == 1)
                            arr[r][c] = temp[r][c]; // 해당 부분 오류 (i, j만큼 이동해주어야 함)
            }
        }
    }
}

 

따라서 오류 코드를 다음과 같이 수정해주었다.

arr[r + i][c + j] = temp[r][c];

 

그러나 이대로 다시 출력해보았는데, 한 번 스티커를 붙이면 그 스티커는 더 이상 순회하지 않고 빠져나와야하는데, 계속 스티커를 붙인 뒤에도 해당 스티커로 다시 탐색을 하고 있었다. 그래서 if (flag) 내부 마지막에 return; 을 추가해주었다.

그랬더니 정답이 나왔다.

전체 코드

#include <iostream>
#include <vector>
using namespace std;
int N, M, K, R, C;
bool check = false;
vector<vector<int>> arr, temp;

void stick() {
    // 전체 위치 순회하여 붙일 수 있는 공간 찾아 붙이기
    for (int i = 0; i <= N - R; ++i) { 
        for (int j = 0; j <= M - C; ++j) {
            bool flag = true;
            for (int r = 0; r < R; ++r)
                for (int c = 0; c < C; ++c) {
                    if (temp[r][c] == 1 && arr[r + i][c + j] == 1) 
                        { flag = false; break; } // 이미 스티커가 붙여있을 경우 종료
                }
            if (flag) { // 해당 스티커 붙이기
                check = true;
                for (int r = 0; r < R; ++r)
                    for (int c = 0; c < C; ++c)
                        if (temp[r][c] == 1)
                            arr[r + i][c + j] = temp[r][c];
                return;
            }
        }
    }
}

void rotate() {
    for (int i = 0; i < 4; ++i) { // 0도, 90도, 180도, 270도
        stick();
        if (check) break; // 스티커 붙었을 경우 회전 종료
        int T = R; R = C; C = T; // R <-> C
        vector<vector<int>> rotated(R, vector<int>(C));
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
                rotated[i][C - j - 1] = temp[j][i];
        temp = rotated;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    arr = vector<vector<int>>(N, vector<int>(M, 0));
    for (int i = 0; i < K; ++i) {
        cin >> R >> C;
        temp = vector<vector<int>>(R, vector<int>(C, 0));
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                cin >> temp[r][c];
        // 똑바로 해도, 90도 회전해도 스티커가 노트북보다 클 경우 스티커 버림
        if ((R > N || C > M) && (R > M || C > N)) continue;
        check = false; // 스티커 부착 여부
        rotate(); // 스티커 회전
    }
    int cnt = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            if (arr[i][j] == 1) cnt++;
    cout << cnt;
    return 0;
}

고민 1

문제를 풀 때 회전하는 부분이 생각해내기가 어려웠다.

일단 나는 R과 C를 서로 바꿔주고 새로 배열을 하나 만들어서, 그곳에 시계방향으로 90도 회전된 배열을 넣어주었다.

int T = R; R = C; C = T; // R <-> C
vector<vector<int>> rotated(R, vector<int>(C));

그리고 R, C를 통해 전체 배열을 돌면서, 90도로 회전한 값을 넣어준다.

처음에는 회전하는 것에 대한 이해가 어려워서 그림으로 하나씩 그려보았는데, 그림에 나온 ①, ② 와 같이 직접 변경되어야 하는 위치를 하나씩 대입해서 나열해보면서 쉽게 규칙을 찾을 수 있었다.

for (int i = 0; i < R; ++i)
    for (int j = 0; j < C; ++j)
        rotated[i][C - j - 1] = temp[j][i];
temp = rotated;

식으로 표현하면 위와 같이 나타낼 수 있다.

고민 2

다른 사람들이 푼 C++ 코드를 보면 다들 시간이 최소 4ms로 나왔다.

왜 내 코드는 20ms일까 생각을 해보면서 다른 사람들이 푼 코드와 비교해보면서 시간을 잡아먹는 부분을 찾아보기로 했다.

 

처음에는 여기가 문제인가 싶어서 해당 부분만 주석처리하고 제출해봤다.

// 똑바로 해도, 90도 회전해도 스티커가 노트북보다 클 경우 스티커 버림
if ((R > N || C > M) && (R > M || C > N)) continue;

하지만 결과는 그냥 20ms로 동일하게 나왔고, 이 문제는 아닌 것 같다. 하지만 해당 부분이 필요 없는 코드였다는 사실을 알게 되었다.

 

혹시 벡터를 사용하여 동적으로 크기를 조정하는 부분에서 메모리 할당 및 해제하는 부분에서 시간이 오래걸리는 건가 싶어서 전부 그냥 배열로 변경해보았다.

#include <iostream>
using namespace std;
int N, M, K, R, C;
bool check = false;
int arr[40][40] = { 0, };
int temp[10][10] = { 0, };

void stick() {
    // 전체 위치 순회하여 붙일 수 있는 공간 찾아 붙이기
    for (int i = 0; i <= N - R; ++i) { 
        for (int j = 0; j <= M - C; ++j) {
            bool flag = true;
            for (int r = 0; r < R; ++r)
                for (int c = 0; c < C; ++c) {
                    if (temp[r][c] == 1 && arr[r + i][c + j] == 1) 
                        { flag = false; break; } // 이미 스티커가 붙여있을 경우 종료
                }
            if (flag) { // 해당 스티커 붙이기
                check = true;
                for (int r = 0; r < R; ++r)
                    for (int c = 0; c < C; ++c)
                        if (temp[r][c] == 1)
                            arr[r + i][c + j] = temp[r][c];
                return;
            }
        }
    }
}

void rotate() {
    for (int i = 0; i < 4; ++i) { // 0도, 90도, 180도, 270도
        stick();
        if (check) break; // 스티커 붙었을 경우 회전 종료
        int T = R; R = C; C = T; // R <-> C
        int rotated[10][10] = { 0, };
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
                rotated[i][C - j - 1] = temp[j][i];
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
                temp[i][j] = rotated[i][j];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < K; ++i) {
        cin >> R >> C;
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                cin >> temp[r][c];
        check = false; // 스티커 부착 여부
        rotate(); // 스티커 회전
    }
    int cnt = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            if (arr[i][j] == 1) cnt++;
    cout << cnt;
    return 0;
}

이전보다 총 4ms가 줄어들긴 했으나, 16ms는 다른 정답 코드들의 4ms에 비하면 시간이 길게 나왔다. 사실상 큰 차이는 없다.. rotate() 함수의 for 문을 main() 함수로 빼내었더니 그냥 다시 20ms가 되어버렸다.

아예 로직에 문제가 있는 듯했는데 다른 코드들과 별반 다를게 없다.. 뭘까

전체 코드

#include <iostream>
using namespace std;
int N, M, K, R, C;
bool check = false;
int arr[40][40] = { 0, };
int temp[10][10] = { 0, };

void stick() {
    // 전체 위치 순회하여 붙일 수 있는 공간 찾아 붙이기
    for (int i = 0; i <= N - R; ++i) { 
        for (int j = 0; j <= M - C; ++j) {
            bool flag = true;
            for (int r = 0; r < R; ++r)
                for (int c = 0; c < C; ++c) {
                    if (temp[r][c] == 1 && arr[r + i][c + j] == 1) 
                        { flag = false; break; } // 이미 스티커가 붙여있을 경우 종료
                }
            if (flag) { // 해당 스티커 붙이기
                check = true;
                for (int r = 0; r < R; ++r)
                    for (int c = 0; c < C; ++c)
                        if (temp[r][c] == 1)
                            arr[r + i][c + j] = temp[r][c];
                return;
            }
        }
    }
}

void rotate() {
    int T = R; R = C; C = T; // R <-> C
    int rotated[10][10] = { 0, };
    for (int i = 0; i < R; ++i) // 시계방향 90도 회전
        for (int j = 0; j < C; ++j)
            rotated[i][C - j - 1] = temp[j][i];
    for (int i = 0; i < R; ++i) // 원래 배열에 넣기
        for (int j = 0; j < C; ++j)
            temp[i][j] = rotated[i][j];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < K; ++i) {
        cin >> R >> C;
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                cin >> temp[r][c];
        check = false; // 스티커 부착 여부
        for (int i = 0; i < 4; ++i) { // 0도, 90도, 180도, 270도
            stick();
            if (check) break; // 스티커 붙었을 경우 회전 종료
            rotate(); // 스티커 회전
        }
    }
    int cnt = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            if (arr[i][j] == 1) cnt++;
    cout << cnt;
    return 0;
}

 

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

18808번: 스티커 붙이기