백준 2636 치즈

백준 2636번을 풀었다. 한 번 녹일때 치즈의 겉만 녹인다, 라는 재미있는 조건이 있었는데, 이를 어떻게 처리해야 할 지에 대해 고민하게 해 준 문제였다.

시도 1 - 오답

#include <iostream>
#include <vector>
#include <queue>
#define MAX_VAL 100

using namespace std;

struct point {
    int x;//j
    int y;//i
};

queue<point> tempQueue;
queue<point> processingQueue;
queue<point> saveQueue;

int dX[] = { -1, 0, 1, 0 };
int dY[] = { 0, -1, 0, 1 };

int main(void) {
    int tY, tX;
    cin >> tY >> tX;
    vector<vector<int>> table(tY, vector<int>(tX, 0));
    vector<vector<bool>> checked(tY, vector<bool>(tX, 0));

    int day = 0;
    for (int i = 0; i < tY; i++) {
        for (int j = 0; j < tX; j++) {
            cin >> table[i][j];
        }
    }

    processingQueue.push({ 0, 0 });
    checked[0][0] = true;


    int checkCnt = 1;
    while (!processingQueue.empty()) {
        day++;
        while (!processingQueue.empty()) {

            point now = processingQueue.front();
            checked[now.y][now.x] = true;
            table[now.y][now.x] = 0;
            processingQueue.pop();

            for (int i = 0; i < 4; i++) {
                int nextX = now.x + dX[i];
                int nextY = now.y + dY[i];

                bool canGoCondition = nextX >= 0 && nextX < tX&& nextY >= 0 && nextY < tY && !checked[nextY][nextX];
                if (canGoCondition) {
                    if (table[nextY][nextX] == 1) {
                        tempQueue.push({ nextX, nextY });
                        if (checked[nextY][nextX] == false) {
                            checked[nextY][nextX] = true;
                            checkCnt++;
                        }
                    }
                    else {
                        processingQueue.push({ nextX, nextY });
                        if (checked[nextY][nextX] == false) {
                            checked[nextY][nextX] = true;
                            checkCnt++;
                        }
                    }
                }
            }
        }
        while (!tempQueue.empty()) {
            point nextPoint = tempQueue.front();
            processingQueue.push(nextPoint);
            saveQueue.push(nextPoint);
            tempQueue.pop();

            table[nextPoint.y][nextPoint.x] = 0;
        }

        if (checkCnt >= tX * tY) break;
        while (!saveQueue.empty()) {
            saveQueue.pop();
        }

    }

    int result = 0;
    while (!saveQueue.empty()) {
        saveQueue.pop();
        result++;
    }

    cout << day << "\n" << result;

    return 0;
}

위 코드로 95% 테스트 케이스를 통과하지 못하였다.

내가 틀린 반례는 아래와 같다.

즉, 내 코드는 모든 테이블을 다 확인하는 것이 탈출 조건이었고 한 번 돌면서 확인할 떄마다(bfs 할 때마다) 하루가 걸렸다.

나의 코드의 경우 위 테스트 케이스 결과가 2, 0이 나왔다. 다 돌아보는데 이틀이 걸리고 그 전날 있던 치즈는 0이라는 결과가 나온 것이다.

시도 2 - 정답

이를 해결하기 위해서 탈출 조건을 수정하였다.

원래 : 모든 테이블을 다 체크했을 경우 탈출

변경 : 모든 치즈를 다 검토했을 경우 탈출

바뀐 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX_VAL 100

using namespace std;

struct point {
    int x;//j
    int y;//i
};

queue<point> tempQueue;
queue<point> processingQueue;
queue<point> saveQueue;

int dX[] = { -1, 0, 1, 0 };
int dY[] = { 0, -1, 0, 1 };

int main(void) {
    int tY, tX;
    cin >> tY >> tX;
    vector<vector<int>> table(tY, vector<int>(tX, 0));
    vector<vector<bool>> checked(tY, vector<bool>(tX, 0));
    int cheeseCnt = 0;
    int cheeseCheckCnt = 0;
    int day = 0;
    for (int i = 0; i < tY; i++) {
        for (int j = 0; j < tX; j++) {
            int num;
            cin >> num;
            table[i][j] = num;
            if(num == 1) cheeseCnt++;
        }
    }

    processingQueue.push({ 0, 0 });
    checked[0][0] = true;

    while (!processingQueue.empty()) {
        day++;
        while (!processingQueue.empty()) {//치즈 겉을 녹이는 동작

            point now = processingQueue.front();
            checked[now.y][now.x] = true;
            table[now.y][now.x] = 0;
            processingQueue.pop();

            for (int i = 0; i < 4; i++) {
                int nextX = now.x + dX[i];
                int nextY = now.y + dY[i];

                bool canGoCondition = nextX >= 0 && nextX < tX&& nextY >= 0 && nextY < tY && !checked[nextY][nextX];
                if (canGoCondition) {
                    if (table[nextY][nextX] == 1) {//확인한 곳이 치즈라면
                        tempQueue.push({ nextX, nextY });//다음에 BFS를 시작한 큐에 넣고
                        checked[nextY][nextX] = true;//방문을 체크하고
                        cheeseCheckCnt++;//확인한 치즈 개수를 올린다.

                    }
                    else {//확인한 곳이 치즈가 아니라면
                        processingQueue.push({ nextX, nextY });//당장 방문할 큐에 넣고
                        checked[nextY][nextX] = true;//방문을 체크한다.
                    }
                }
            }
        }
        while (!tempQueue.empty()) {//다음에 BFS를 시작할 큐에서 바로 사용할 큐로 요소를 옮긴다.
            point nextPoint = tempQueue.front();
            processingQueue.push(nextPoint);
            saveQueue.push(nextPoint);//정답으로 사용될 큐
            tempQueue.pop();
        }

        if (cheeseCheckCnt == cheeseCnt) break;//종료 조건 : 치즈 개수가 다 채워짐
        while (!saveQueue.empty()) {//정답으로 사용될 큐를 비움
            saveQueue.pop();
        }
    }

    int result = 0;
    while (!saveQueue.empty()) {//정답의 개수를 확인
        saveQueue.pop();
        result++;
    }

    cout << day << "\n" << result;

    return 0;
}

드디어 정답이다.

저작자표시 비영리 변경금지