백준 11559번: Puyo Puyo

 문제설명 

 

1. 주어진 뿌요뿌요 룰에따라 몇콤보가 나오는지 출력하면됨 .

 

 알고리즘 

 

1. 뿌요를 밑으로 내려주는 함수 down() 설계

 

2. 뿌요가 4개이상붙어있는지 확인하는 dfs_size함수 설계 

   - dfs 를 이용하여 같은 문자일때만 재귀 호출 하였고 마지막에 깊이를 return 하였다.

 

3. 뿌요가 4개이상일때 터트리는 함수 설계.

    - dfs_size 함수를 이용하여 뿌요의갯수가 4개이상임을 확인하였을때 뿌요를 터트렸다

    - 그리고 뿌요가 터지면 while 문을 한번더 돌게 하는 논리형 변수를 수정하였다.

 

 코드 

 

#include<iostream>
 
 
using namespace std;
char map[13][7];
int visited[13][7];
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
 
void down() { // 밑으로 내려주는 함수
    for (int i = 11; i > 0; i--) {
        for (int j = 0; j < 6; j++) {
            if (map[i][j] == '.') {
                if (map[i - 1][j] != '.') {
                    map[i][j] = map[i - 1][j];
                    map[i - 1][j] = '.';
                }
                else if (i-2>=0&&map[i - 2][j] != '.') {
                    map[i][j] = map[i - 2][j];
                    map[i - 2][j] = '.';
                }
                else if (i - 3 >= 0 && map[i - 3][j] != '.') {
                    map[i][j] = map[i - 3][j];
                    map[i - 3][j] = '.';
                }
                else if (i - 4 >= 0 && map[i - 4][j] != '.') {
                    map[i][j] = map[i - 4][j];
                    map[i - 4][j] = '.';
                }
            }
        }
    }
}
bool pos = false;
int pos_cnt = 0;
void dfs_size(int y, int x, char C) {
    
    if (visited[y][x]) {
        return;
    }
    visited[y][x] = 1;
 
    for (int i = 0; i < 4; i++) {
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        if (next_x >= 0 && next_x < 6 && next_y >= 0 && next_y < 12) {
            if (!visited[next_y][next_x] && map[next_y][next_x] == C) {
                dfs_size(next_y, next_x, C);
                pos_cnt++;
            }
        }
    }
}
 
void dfs(int y, int x, char C) {
    if (visited[y][x]) {
        return;
    }
    visited[y][x] = 1;
    map[y][x] = '.';
    for (int i = 0; i < 4; i++) {
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        if (next_x >= 0 && next_x < 6 && next_y >= 0 && next_y < 12) {
            if (!visited[next_y][next_x] && map[next_y][next_x] == C) {
                map[next_y][next_x] = '.';
                dfs(next_y, next_x, C);
            }
        }
    }
}
void reset() {
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            visited[i][j] = 0;
        }
    }
}
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int ans = 0;
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> map[i][j];
        }
    }
    bool next = false;
    while (1) {
        
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
 
                if (map[i][j] != '.') {
                    //뿌요가 몇개씩 붙어있는지
                    dfs_size(i, j, map[i][j]);                    
                    reset();
                    //뿌요가 터질수있으면 터트리기.
                    if (pos_cnt>=3) {
                        dfs(i, j, map[i][j]);
                        next = true;
                    }
                    pos_cnt = 0;
                }
    
            }
 
        }
        //뿌요 밑으로 내리기 ! 
        down();        
 
        //뿌요가 터지지않으면 break
        if (!next)break;
        //방문 초기화
        reset();
        //next 초기화
        next = false;
        //콤보 ++
        ans++;
    }
 
    cout << ans;
}