[ 백준 ] 16924 / 십자가 찾기

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
154/228
post-thumbnail

# Appreciation

/*
 * Problem :: 16924 / 십자가 찾기
 *
 * Kind :: Simulation
 *
 * Insight
 * - 십자가로 주어진 모양을 만들 수 있는가?
 *   + 만들 수 있는지 없는지만 판별하면 된다
 *     # 만들 수 있는 경우, 십자가의 최소 개수를 구하지 않아도 된다
 *       -> 그냥 십자가 놓을 수 있으면 다 놓아보고 판단하면 되지 않을려나?
 *
 * - 시간 복잡도를 정확히 계산하기가 꽤나 복잡하다
 *   + 각 점을 기준으로 십자가를 놓을 때 최대 s 의 범위가 달라진다
 *     # 근데 max(N,M)=100 이라서 O(N^4) 까지 괜찮은데
 *       이정도면 다 놓아봐도 괜찮을 것 같다 => 실제로 괜찮았다
 *
 * Point
 * - 주어진 모양을 만들 수 있는 최소 십자가의 개수를 구하는 것이 아니다
 *   그냥 모양만 만들면 된다
 *   + 실제로 모양이 만들어졌는지 확인하기 위한 배열이 필요하다
 *
 * - 문제는 왼쪽 맨 윗칸을 (1,1) 로 설정했지만
 *   코드에서는 편의상 (0,0) 으로 보았다
 *   + 십자가 정보 넣을 때 (+1,+1) 만 해주면 문제푸는데 아무상관 없다
 *
 * - 십자가 개수가 N*M 개 이하여야 하는데
 *   어차피 십자가 최소크기가 1 이고 기본적으로 5칸을 차지해서
 *   절대 십자가 개수가 N*M 개 되는 일은 없다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N, M;
char board[100][100];
bool isChecked[100][100];
struct Cross { int x, y, s; };
int dx[4] = {+1, 0, 0, -1};
int dy[4] = {0, +1, -1, 0};
#define INF 987654321

// Set up : Functions Declaration
bool isValid(int x, int y);
int getMaxS(int x, int y);
void putCross(int x, int y, int s);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            cin >> board[i][j];
        }
    }

    // Process
    int k = 0; /* 십자가의 개수 */
    vector<Cross> crosses; /* 십자가이 정보가 담긴 Vector */
    for (int x=1; x<N-1; x++) { /* 문제에서는 시작칸이 (1,1)
                                 * 코드에서는 시작칸이 (0,0) */
        for (int y=1; y<M-1; y++) { /* (0~(N-1), 0) 과 (0, 0~(M-1) 에는
                                     * 십자가를 놓을 수 없음
                                     * 그래서 (1~(N-2), 1~(M-2)) 칸만 탐색 */
            if (board[x][y] == '*') { /* 현재칸이 별표면 */
                int s = getMaxS(x, y); /* 이 칸을 중심으로
                                        * 십자가를 놓을 때 최대 크기를 구함 */
                if (s >= 1) { /* 최대 크기가 1 이상이면 */
                    putCross(x, y, s); /* 십자가를 놓음 */
                    k++; /* 십자가 개수 갱신 */
                    crosses.push_back({x+1, y+1, s}); /* 십자가 정보 저장 */
                }
            }
        }
    }

    // Control : Output
    bool isPossible = true; /* 주어진 모양을 만들 수 있는지 여부 */
    for (int x=0; x<N; x++) {
        if (not(isPossible)) break;
        for (int y=0; y<M; y++) {
            /* 별표인 칸인데 체크안된 칸이 있으면 */
            if (board[x][y] == '*' && not(isChecked[x][y])) {
                isPossible = false; /* 모양 만들기 불가능 */
                break;
            }
        }
    }

    if (not(isPossible))
        cout << -1 << endl;
    else {
        cout << k << endl;
        for (Cross c : crosses) {
            cout << c.x << ' ' << c.y << ' ' << c.s << endl;
        }
    }
}

// Helper Functions
bool isValid(int x, int y)
/* 주어진 좌표가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return x >= 0 && x < N && y >= 0 && y < M;
}

int getMaxS(int x, int y)
/* 주어진 좌표에서 놓을 수 있는 십자가의 최대 크기를 구함 */
{
    int maxS = INF;
    for (int i=0; i<4; i++) { /* 아래쪽, 오른쪽, 왼쪽, 위쪽 차례로 검사
                               * 각 방향으로 놓아진 별표의 개수의 최솟값이
                               * 십자가의 최대 크기 */
        int s = 0; /* (x,y) 에서 (dx[i], dy[i]) 방향으로 놓아진 별표의 개수 */
        int ax = x + dx[i];
        int ay = y + dy[i];
        while (isValid(ax, ay) && board[ax][ay] == '*') {
            s++;
            ax += dx[i];
            ay += dy[i];
        }
        maxS = min(maxS, s); /* 십자가의 최대 크기 갱신 */
    }
    return maxS;
}

void putCross(int x, int y, int s)
/* (x,y) 에 크기 s 인 십자가를 놓음 */
{
    isChecked[x][y] = true;
    for (int i=1; i<=s; i++) {
        isChecked[x+i][y] = true;
        isChecked[x-i][y] = true;
        isChecked[x][y+i] = true;
        isChecked[x][y-i] = true;
    }
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글