[BaekJoon] 11559 Puyo Puyo :: monton

문제

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

풀이

어릴적에 했던 게임인 뿌요뿌요 문제이다

이 문제는 dfs+시뮬레이션 문제

 

특징이 4개 이상이 상하좌우로 붙어 있는 뿌요는 터지고 차례로 아래로 떨어져야 한다

4개 이상이 붙어있는지 확인하고 아래로 떨어지게만 구현을 잘해주면 어려움 점이 없을 거 같다

나는 틀렸던 이유가 한번 터진 뿌요들을 각각 카운트 해주는 것이 아니라

현 상황에서 여러개가 터졌다면 한 번으로 카운트 해야한다

코드

#include <iostream>
using namespace std;
 
char arr[13][7];
int ans, cnt,flag,chknum;
int visit[13][7];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
void init() {
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            visit[i][j] = 0;
        }
    }
}
 
void func(int x, int y, char c) {
    if (x < 0 || x >= 12 || y < 0 || y >= 6) return;
    if (visit[x][y]) return;
    if (arr[x][y] != c) return;
 
    chknum++;
    visit[x][y] = 1;
 
    for (int i = 0; i < 4; i++) {
        func(x + dir[i][0], y + dir[i][1], c);
    }
}
 
int chkans() {
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            if (arr[i][j] >= 'A'&&arr[i][j] <= 'Z') {
                chknum = 0;
                func(i, j, arr[i][j]);
                if (chknum >= 4) return 0;
            }
        }
    }
    return 1;
}
 
void dfs(int x, int y, char c) {
    if (x < 0 || x >= 12 || y < 0 || y >= 6) return;
    if (visit[x][y]) return;
    if (arr[x][y] != c) return;
    
    cnt++;
    visit[x][y] = 1;
 
    if (cnt >= 4) {
        flag = 1;
    }
    
 
    for (int i = 0; i < 4; i++) {
        dfs(x + dir[i][0], y + dir[i][1],c);
    }
}
 
int main() {
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> arr[i][j];
        }
    }
 
    while (1) {
 
        init();
        if (chkans()) {
            cout << ans;
            return 0;
        }
 
        init();
 
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (arr[i][j] >= 'A'&&arr[i][j] <= 'Z') {
                    init();
                    cnt = flag = 0;
                    dfs(i, j, arr[i][j]);
                    if (flag) { 
                        for (int i = 0; i < 12; i++) {
                            for (int j = 0; j < 6; j++) {
                                if (visit[i][j])arr[i][j] = '.';
                            }
                        }
                    }
                }
            }
        }
 
        for (int j = 0; j < 6; j++) {
            int a = 11;
            for (int i = 11; i >= 0; i--) {
                if (arr[i][j] >= 'A'&&arr[i][j] <= 'Z') {
                    if (a != i) {
                        arr[a][j] = arr[i][j];
                        arr[i][j] = '.';
                    }
                    a--;
                }
            }
 
        }
        ans++;
    }
}