[C++]백준 28256번 초콜릿 보관함

📌문제 링크

---

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

📌문제 설명

---

3x3이라 크기가 작아 브루트포스로도 가능하고 그래프로도 풀이가 가능합니다. flood fill 느낌의 bfs로 해결했습니다. 그룹별 인원수를 vector에 입력하여 정렬 후, 입력에서 들어온 test vector와 동일하면 1 동일하지 않으면 0을 출력합니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> answer; // 정답을 저장할 벡터
vector<int> test;   // 테스트용 벡터
char mp[4][4];      // 4x4 맵
bool visited[4][4]; // 방문 여부를 체크할 배열
int T, cnt, k;      // T: 테스트 케이스 수, cnt: 카운터, k: 특정 값
int dx[4] = {0, 0, 1, -1}; // x축 이동 배열
int dy[4] = {1, -1, 0, 0}; // y축 이동 배열

// 초기화 함수
void init() {
    answer.clear(); // 정답 벡터 초기화
    test.clear();   // 테스트 벡터 초기화
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            visited[i][j] = false; // 방문 배열 초기화
        }
    }
}

// 너비 우선 탐색 함수
int bfs(int startX, int startY) {
    queue<pair<int, int>> q;
    q.push({startX, startY});
    visited[startX][startY] = true; // 시작 위치 방문 처리
    int size = 1; // 연결된 칸의 개수

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; // 새로운 x 좌표
            int ny = y + dy[i]; // 새로운 y 좌표

            // 범위를 벗어나거나 방문했거나 장애물인 경우 무시
            if(nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && !visited[nx][ny] && mp[nx][ny] == 'O'){
                visited[nx][ny] = true; // 방문 처리
                q.push({nx, ny}); // 큐에 추가
                size++; // 연결된 칸의 개수 증가
            }
        }
    }

    return size; // 탐색 결과 반환
}

// 테스트 케이스 해결 함수
void solve() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (mp[i][j] == 'O' && !visited[i][j]) {
                answer.push_back(bfs(i, j)); // 연결된 칸의 개수를 정답 벡터에 추가
            }
        }
    }
    sort(answer.begin(), answer.end()); // 정답 벡터 정렬
    if(answer == test){ // 정답 벡터와 테스트 벡터가 같다면
        cout << "1\n"; // 1 출력
    }
    else{
        cout << "0\n"; // 0 출력
    }
}

// 입력 처리 함수
void input() {
    cin >> T; // 테스트 케이스 수 입력
    while (T--) {
        init(); // 초기화 함수 호출
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cin >> mp[i][j]; // 맵 입력
            }
        }
        cin >> k; // 테스트 벡터 크기 입력
        test.resize(k); // 테스트 벡터 크기 조정
        for (auto &it : test) {
            cin >> it; // 테스트 벡터 값 입력
        }
        solve(); // 테스트 케이스 해결 함수 호출
    }
}

int main() {
    ios::sync_with_stdio(0); // 입출력 속도 향상
    cin.tie(0); // 입력 스트림과 출력 스트림을 분리
    cout.tie(0); // 출력 스트림과 입력 스트림을 분리
    input(); // 입력 처리 함수 호출
    return 0; // 프로그램 종료
}