[BOJ/Silver 2] 백준 28256 초콜릿 보관함(C++)

문제 링크

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

28256번: 초콜릿 보관함

 

문제

코코는 3 × 3의 사각 격자 모양의 초콜릿 보관함을 갖고 있다. 이 보관함은 가운데 칸이 막혀 있고 그 자리에 숫자를 표시하는 화면이 붙어 있다. 나머지 8칸에는 초콜릿을 최대 하나씩 보관할 수 있다.

화면에는 숫자가 최대 4개까지 표시되고, 각각의 숫자는 초콜릿이 들어있는 연결된 칸의 개수를 나타낸다. 숫자가 여러 개이면 오름차순으로 표시된다. 두 칸이 한 변을 따라 맞닿아 있으면 그 두 칸은 연결되어 있다고 한다.

코코는 똑같은 초콜릿 보관함을 하나 더 만들어서 한별이에게 선물하려고 한다. 버그가 있을지 모른다고 걱정하는 코코를 위해, 보관함의 테스트를 도와주자.

 

입력

첫 줄에는 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 100)

각 테스트 케이스는 4줄로 이루어져 있다. 첫 3줄에는 초콜릿 보관함의 상태가 주어진다. O는 그 칸에 초콜릿이 있음, X는 없음을 뜻하며, 가운데 칸은 -로 표시된다. 4번째 줄에는 화면에 표시된 숫자의 개수 n과 숫자의 목록 a1, a2, ⋯, an이 순서대로 주어진다. (0 ≤ n ≤ 4, 1 ≤ a1 ≤ a2 ≤ ⋯ ≤ an ≤ 8)

 

출력

각 테스트 케이스마다, 화면의 표시가 올바르다면 1, 아니라면 0을 출력한다.

 

예제 입력 1

6
OOO
O-O
XOO
1 7
XOO
O-O
XXO
2 1 4
OXO
O-X
XXO
3 1 1 2
XOX
O-O
XOX
4 1 1 1 1
XOO
O-O
OOX
1 6
OXX
O-O
XXO
3 1 1 2

예제 출력 1

1
1
1
1
0
0

 

알고리즘 분류

• 그래프 탐색

 

풀이

초콜릿이 들어있는 연결된 칸 수들을 BFS를 통해 구한다. 그리고 벡터에 그 값들을 push하고 오름차순 정렬한다.

그리고 화면에 표시된 숫자의 개수들을 담은 벡터와 비교하여 같다면 1, 다르다면 0을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 3
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int T, N;
char MAP[MAX][MAX];
vector<int> Vec, Vec2;
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };

void init() {
    Vec.clear();
    Vec2.clear();
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            Visited[i][j] = false;
        }
    }
}

int BFS(int Y, int X) {
    queue<pair<int, int> > Q;
    Visited[Y][X] = true;
    Q.push(make_pair(Y, X));
    int Result = 1;

    while (!Q.empty()) {
        int NowY = Q.front().first;
        int NowX = Q.front().second;
        Q.pop();
        
        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 0) && (NextY < MAX) && (NextX >= 0) && (NextX < MAX) && !Visited[NextY][NextX]) {
                if (MAP[NextY][NextX] == 'O') {
                    Result++;
                    Visited[NextY][NextX] = true;
                    Q.push(make_pair(NextY, NextX));
                }
            }
        }
    };

    return Result;
}

void settings() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if ((MAP[i][j] == 'O') && !Visited[i][j]) {
                Vec2.push_back(BFS(i, j));
            }
        }
    }
    sort(Vec2.begin(), Vec2.end());
}

bool Comp() {
    if (Vec == Vec2) {
        return true;
    }
    return false;
}

void find_Answer() {
    if (Comp()) {
        cout << "1\n";
    }
    else {
        cout << "0\n";
    }
}

void input() {
    cin >> T;
    while (T--) {
        for (int i = 0; i < MAX; i++) {
            string S;
            cin >> S;
            for (int j = 0; j < MAX; j++) {
                MAP[i][j] = S[j];
            }
        }
        cin >> N;
        init();
        Vec.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> Vec[i];
        }
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}