(C++) 5656. [모의 SW 역량테스트] 벽돌 깨기

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

로직은 Java와 같음.
– 가지의 수는  (numW)^numN 이다. 여기서 numW는 최대 12이고 N은 최대 4이므로 최대 20736개의 경우를 계산해 보면 됨. DFS를 쓰면 됨.
– 선택된 column에서 가장 위의 벽돌이 어딘지 우선 탐색. (만약 벽돌이 없으면 변화가 안 생기기 때문에 바로 다음 단계로 넘어감) 그리고 그 벽돌을 removeMap에 등록 (removeMap: 제거할 벽돌 목록)
– 그 벽돌을 시작으로 해서 같이 깨지는 벽돌을 모두 탐색함. 최초 벽돌에 1차 영향을 받는 벽돌들을 removeMap에 추가하고, 크기가 1보다 큰 벽돌은 queue에 추가함.
– 이후 queue가 빌 때까지 영향 받는 벽돌 탐색 및 queue 추가 (벽돌 숫자가 1보다 큰 경우)를 수행. 단, 한 번 removeMap에 추가된 벽돌은 다시 queue 추가하지 않음.
– removeMap 작성이 완료되면 이후 필요한 벽돌들을 모두 제거한 후, 밑으로 끌어당기는 작업 수행.
– 벽돌들이 모두 밑으로 내려오면 다음 단계로 넘어감. 단 최대 단계까지 이미 수행한 경우, 남은 벽돌 수를 세서 최소값인 경우만 저장.

#include <iostream>
#include <cstdlib>
//#include <cstdio>

using namespace std;

int numN = 0, numW = 0, numH = 0;
int minBlocks = 0;

void process(int** map);
void process_(int numTry, int theColumn, int** map);

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

	int test_case;
	int T;
	
	//freopen("input.txt", "r", stdin);
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
        cout << '#' << test_case << ' ';

        cin >> numN >> numW >> numH;
        
        int** map; // int map[numH][numW]; row index, column index
        map = (int**) malloc (numH * sizeof(int*));
        for (int i = 0; i < numH; i++)
            map[i] = (int*) malloc (numW * sizeof(int));

        for (int i = 0; i < numH; i++) {
            for (int j = 0; j < numW; j++) {
                cin >> map[i][j];
            }
        }

        // Let's solve by DFS
        minBlocks = numH * numW;
        process(map);

        // print result
        cout << minBlocks << '\n';
	}
	return 0;
}

void process(int** map) {
    for (int i = 0; i < numW; i++)
        process_(1, i, map);
}

void process_(int numTry, int theColumn, int** map) {
    // copied map
    int** newMap; // int newMap[numH][numW]; row index, column index
    newMap = (int**) malloc (numH * sizeof(int*));
    for (int i = 0; i < numH; i++)
        newMap[i] = (int*) malloc (numW * sizeof(int));

    // marked as remove map
    int** removeMap; // int newMap[numH][numW]; row index, column index
    removeMap = (int**) malloc (numH * sizeof(int*));
    for (int i = 0; i < numH; i++)
        removeMap[i] = (int*) malloc (numW * sizeof(int));

    // copy the map
    for (int i = 0; i < numH; i++) {
        for (int j = 0; j < numW; j++) {
            newMap[i][j] = map[i][j];
            removeMap[i][j] = 0;
        }
    }

    if (newMap[numH - 1][theColumn] != 0) { // if there is any block in this column, then proceed
        // find the topmost block in the column
        int theRow = -1;
        for (int i = 0; i < numH; i++) {
            if (newMap[i][theColumn] != 0) {
                theRow = i;
                break;
            }
        }

        // find other blocks need to be removed
        int* queueRow; //[numH * numW];
        int* queueColumn;
        int front = -1;
        int rear = -1;

        queueRow = (int*) malloc (numH * numW * sizeof(int));
        queueColumn = (int*) malloc (numH * numW * sizeof(int));

        if (front == -1)
            front = 0;
        
        rear++;
        queueRow[rear] = theRow;
        queueColumn[rear] = theColumn;

        removeMap[theRow][theColumn] = 1;

        while (front != -1 && front <= rear) { // while the queue is not empty
            int myRow = queueRow[front];
            int myColumn = queueColumn[front];
            front++; // dequeue

            int mySize = newMap[myRow][myColumn];
            if (mySize == 1) // value is 1: it breaks alone
                continue;

            int upperBound = 0, lowerBound = 0, leftBound = 0, rightBound = 0;
            
            upperBound = myRow - (mySize - 1);
            if (upperBound < 0)
                upperBound = 0;

            lowerBound = myRow + (mySize - 1);
            if (lowerBound > numH - 1)
                lowerBound = numH - 1;

            leftBound = myColumn - (mySize - 1);
            if (leftBound < 0)
                leftBound = 0;

            rightBound = myColumn + (mySize - 1);
            if (rightBound > numW - 1)
                rightBound = numW - 1;

            for (int i = myRow - 1; i >= upperBound; i--) {
                if (removeMap[i][myColumn] == 0) {
                    removeMap[i][myColumn] = 1;

                    if (newMap[i][myColumn] > 1) {
                        rear++;
                        queueRow[rear] = i;
                        queueColumn[rear] = myColumn;
                    }
                }
            }
            for (int i = myRow + 1; i <= lowerBound; i++) {
                if (removeMap[i][myColumn] == 0) {
                    removeMap[i][myColumn] = 1;

                    if (newMap[i][myColumn] > 1) {
                        rear++;
                        queueRow[rear] = i;
                        queueColumn[rear] = myColumn;
                    }
                }
            }
            for (int i = myColumn - 1; i >= leftBound; i--) {
                if (removeMap[myRow][i] == 0) {
                    removeMap[myRow][i] = 1;

                    if (newMap[myRow][i] > 1) {
                        rear++;
                        queueRow[rear] = myRow;
                        queueColumn[rear] = i;
                    }
                }
            }
            for (int i = myColumn + 1; i <= rightBound; i++) {
                if (removeMap[myRow][i] == 0) {
                    removeMap[myRow][i] = 1;

                    if (newMap[myRow][i] > 1) {
                        rear++;
                        queueRow[rear] = myRow;
                        queueColumn[rear] = i;
                    }
                }
            }
        }

        // remove map according to the removeMap info
        for (int i = 0; i < numH; i++) {
            for (int j = 0; j < numW; j++) {
                if (removeMap[i][j] == 1)
                    newMap[i][j] = 0;
            }
        }

        // move the blocks downward
        for (int i = 0; i < numW; i++) {
            int downmostBlankRow = -1;
            for (int j = numH - 1; j >= 0; j--) {
                if (downmostBlankRow == -1 && newMap[j][i] == 0) // first mark the blank space
                    downmostBlankRow = j;
                else if (downmostBlankRow != -1 && newMap[j][i] > 0) { // if the block need to be moved
                    newMap[downmostBlankRow][i] = newMap[j][i];
                    newMap[j][i] = 0;
                    downmostBlankRow--;
                }
            }
        }
    }
    //else ; // no need to proceed if there is no block in this column (no change)

    for (int i = 0; i < numH; i++)
        free(removeMap[i]);
    free(removeMap);

    if (numTry == numN) { // calculate remaining blocks
        int blocks = 0;
        for (int i = 0; i < numH; i++) { 
            for (int j = 0; j < numW; j++) {
                if (newMap[i][j] != 0)
                    blocks++;
            }
        }

        if (blocks < minBlocks)
            minBlocks = blocks;
    }
    else { // proceed
        // if there is no remaining block, then return
        bool noBlocksRemaining = true;
        for (int i = 0; i < numW; i++) {
            if (newMap[numH - 1][i] != 0) {
                noBlocksRemaining = false;
                break;
            }
        }

        // proceed if there is more blocks
        if (noBlocksRemaining == false) {
            for (int i = 0; i < numW; i++)
                process_(numTry + 1, i, newMap);
        }
        else // if there is no blocks remaining, then minBlocks becomes 0
            minBlocks = 0;
    }

    for (int i = 0; i < numH; i++)
        free(newMap[i]);
    free(newMap);
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.