[백준 11559] Puyo Puyo

문제풀이

 

간단한 시뮬레이션 문제이다. 시뮬레이션을 오랜만에 풀어서 그런가.. visited 초기화를 매번해주지않아 빨리 풀 문제에 시간을 좀 쓴거같다. 덕분에 xcode에서 디버깅하는 법을 터득했다..

 

소스코드

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
 
#define ROW_SIZE 12
#define COL_SIZE 6
using namespace std;
 
int Map[ROW_SIZE][COL_SIZE];
 
int dir_row[4] = {1,0,-1,0};
int dir_col[4] = {0,-1,0,1};
bool visited[ROW_SIZE][COL_SIZE];
vector<pair<int,int>> sameGroup;
bool isChanged=false;
bool isPuyo(int next_row, int next_col){
    if(next_row<0||next_col<0||next_row>=ROW_SIZE||next_col>=COL_SIZE)
        return false;
    if(Map[next_row][next_col]=='.')
        return false;
    if(visited[next_row][next_col])
        return false;
    return true;
}
 
void dfs(int r, int c,int color){
    for(int i=0;i<4;i++){
        int next_row = r+ dir_row[i];
        int next_col = c + dir_col[i];
        
        if(isPuyo(next_row, next_col)){
            if(Map[next_row][next_col] == color){ //같은 경우
                visited[next_row][next_col] =true;
                sameGroup.push_back(make_pair(next_row,next_col));
                dfs(next_row,next_col,color);
            }
        }
    }
}
//void printMap(){
//    for(int i=0;i<ROW_SIZE;i++){
//        for(int j=0;j<COL_SIZE;j++){
//            printf("%3d ",Map[i][j]);
//        }
//        printf("\n");
//    }
//}
void eraseSameGroup() {
    for(int i=0;i<ROW_SIZE;i++){
        for(int j=0;j<COL_SIZE;j++){
            if(Map[i][j]>0&&!visited[i][j]){
                sameGroup.push_back(make_pair(i,j));
                visited[i][j]=true;
                dfs(i,j,Map[i][j]);
                if(sameGroup.size()>=4){
                    isChanged = true;
                    for(int k=0;k<sameGroup.size();k++){
                        int row = sameGroup[k].first;
                        int col = sameGroup[k].second;
                        Map[row][col]=-1;
                    }
//                    printf("\n한색삭제후\n");
//                    printMap();
                }
                sameGroup.clear();
            }
        }
    }
}
 
void arrangeCol(int r,int c){
    int cnt=0;
    for(int i=r;i>=0;i--){
        if(Map[i][c]==-1){
            cnt++;
        }
        else{
            break;
        }
    }
    for(int i=r;i>=0;i--){
        if(i-cnt>=0)
            Map[i][c] = Map[i-cnt][c];
        else
            Map[i][c]=0;
    }
}
void initVisited(){
    for(int i=0;i<ROW_SIZE;i++){
        for(int j=0;j<COL_SIZE;j++){
            visited[i][j] = false;
        }
    }
}
int main() {
    
    for(int i=0;i<ROW_SIZE;i++){
        for(int j=0;j<COL_SIZE;j++){
            char input;
            while(1){
                scanf("%c",&input);
                Map[i][j] = input;
                if(input == '.'){//빈공간
                    Map[i][j] = 0;
                    break;
                }
                else if(input>='A' && input<='Z'){//색
                    Map[i][j] = input-'A'+1;
                    break;
                }
            }
        }
    }
    //4개씩 dfs로 없애기
    int result=0;
    while(1){
        isChanged =false;
        initVisited();
        eraseSameGroup();
        if(!isChanged)
            break;
        result++;
//        printf("\n지운후\n");
//        printMap();
        for(int j=0;j<COL_SIZE;j++){
            for(int i=ROW_SIZE-1;i>=0;i--){
                if(Map[i][j]==-1){
                    arrangeCol(i,j);
                }
            }
        }
//        printf("\n정렬후\n");
//        printMap();
    }
    printf("%d\n",result);
    
    return 0;
}

 

문제 링크 : https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo