[BOJ] 11559번 : 미로만들기(C++)

문제 링크 : 백준 11559번

[문제 접근]

범위가 크기 않기 때문에 조건을 전부 탐색해줘도 될 것 같았다.

1. (1,1) -> (12,6)까지 돌면서 뿌요를 발견하면 BFS탐색한다.
2. BFS탐색할 때 같은 뿌요가 4개 이상이면 '.'으로 변경시킨다.
3. 전부 탐색 후 arrange함수로 들어가서 뿌요를 전부 밑으로 내려준다.
   • '.'으로 변경시킨 경우가 없을 경우 break걸고 정답 출력
4. 다시 1번으로

⭐ 어차피 색깔 별로 숫자를 세는 것이 아니기 때문에 색은 크게 상관하지 않았다

[소스 코드]

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
char arr[13][7];
bool visit[13][7];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

bool BFS(char target, int sx, int sy) {
    bool check = false;
    visit[sx][sy] = true;
    queue<pair<int, int> > q;
    queue<pair<int, int> > tmp;
    q.push({sx, sy});
    tmp.push({sx, sy});

    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];
            int ny = y + dy[i];

            if(nx<1 || nx>12 || ny<1 || ny>6) continue;
            if(arr[nx][ny] == target && !visit[nx][ny]) {
                visit[nx][ny] = true;
                q.push({nx, ny});
                tmp.push({nx, ny});
            }
        }
    }

    if(tmp.size()>=4) {
        check = true;
        while(!tmp.empty()) {
            int x = tmp.front().first;
            int y = tmp.front().second;
            tmp.pop();
            arr[x][y] = '.';
        }
    }

    return check;
}

bool go() {
    memset(visit, false, sizeof(visit));
    bool check = false;
    for(int i=1 ; i<=12 ; i++) {
        for(int j=1 ; j<=6 ; j++) {
            if(arr[i][j] == '.') visit[i][j] = true;
            else {
                if(BFS(arr[i][j], i, j)) {
                    check = true;
                }
            }
        }
    }

    return check;
}

void arrange() {
    for(int i=6 ; i>=1 ; i--) {
        int nowx = i, nowy = 12;
        for(int j=12 ; j>=1 ; j--) {
            if(arr[j][i] != '.') {
                char tmp = arr[j][i];
                arr[j][i] = arr[nowy][nowx];
                arr[nowy][nowx] = tmp;
                nowy--;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1 ; i<=12 ; i++) {
        string s;
        cin >> s;
        for(int j=1 ; j<=6 ; j++) {
            arr[i][j] = s[j-1];
        }
    }
    int ans=0;
    while(true) {
        if(go()) {
            arrange();
            ans++;
        } else {
            break;
        }
    }

    cout << ans;

    return 0;
}```