[코드트리] 뿌요뿌요 C++

문제

https://www.codetree.ai/missions/2/problems/puyo-puyo?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획세우기

4방향으로 탐색해야 함 = dx, dy사용

 

같은 수로 이어져 있는 블록만 탐색하게 되므로, 방문하지 않은+다른 수는 직접 찾아줘야 한다 = 이중 for문으로 배열을 돌면서 방문하지 않은 칸에서 DFS 시작

 

DFS를 시작하기 전마다 size를 1로 초기화해주고, 방문시작하는 칸을 체크해줌 (visited[x][y]=true)

 

DFS

방문 가능한지 체크

• 배열 범위를 벗어났으면 false 
• 이미 방문한 칸이면 false
• 현재 칸과 다른 숫자가 적힌 칸이면 false

위 3개 칸에 해당하지 않으면 다음 칸 방문체크(visited[nx][ny]=true)+size 증가(size++)

 

DFS가 끝난 후

• size가 4보다 크면 터트린다고 했으므로 numOfExplode 1증가
• max_size 갱신

 

풀이

#include <iostream>

using namespace std;

int n, size=1, numOfExplodingBlock, maxBlockSize;
int board[101][101];
bool visited[101][101]={false, };

bool InRange(int x, int y){
    return x>=0 && x<n && y>=0 && y<n;
}

bool CanGo(int nx, int ny, int num){
    //cout << nx << " "  << ny <<'\n';
    // 범위를 벗어남
    if(!InRange(nx, ny)) return false;
    // 이미 방문했던 경우 || 다른 숫자
    if(visited[nx][ny] || board[nx][ny]!=num) return false;
    return true;
}

void DFS(int x, int y){
    // 상(-1,0) 하(1,0) 좌(0,-1) 우(0,1)
    int dx[4]={-1, 1, 0, 0};
    int dy[4]={0, 0, -1, 1};

    for(int dir=0; dir<4; ++dir){
        int nx=x+dx[dir], ny=y+dy[dir];

        if(CanGo(nx, ny, board[x][y])){
            visited[nx][ny]=true;
            size++;
            DFS(nx, ny);
        }
    }

}
int main() {
    // input
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> board[i][j];
        }
    }
	
    // solution
    for(int i=0; i<n; i++){
        for(int j=0; j<n; ++j){
            if(visited[i][j]) continue;

            size=1;
            visited[i][j]=true;
            DFS(i, j);

            maxBlockSize = max(maxBlockSize, size);
            if(size>=4) numOfExplodingBlock++;
        }
    }
	
    // output
    cout << numOfExplodingBlock << " " << maxBlockSize <<'\n';
    return 0;
}