[코드트리/DFS] 뿌요뿌요

문제

https://www.codetree.ai/trails/complete/curated-cards/test-puyo-puyo/description

Code Tree | Learning to Code with Confidence

 

해결방법

해당 문제를 해결하려면 칸을 전체 순회하며 블럭의 수, 블럭의 크기를 구해야한다. 이때 전체 순회를 하며 블럭(상하좌우 인접한 칸들이 같은 값을 가진 그룹)을 찾는 방법으로는 기본적인 dfs로 구현할 수 있다. 그리고 dfs로 블럭을 구하는동안 블럭의 칸 갯수를 구해야한다. 해당 과정을 수행하기 위해 나는 재귀함수로 dfs메소드를 구현하였고 각각의 단계는 다음과 같다.

1. 칸 카운트 1 초기화
   
   • 1로 초기화함으로써 현재 칸 하나를 의미한다.
2. 0...4 반복문으로 상하좌우 칸 탐색
   • 맵의 범위를 벗어나지 않고, 이미 방문하지 않았으며, 현재 칸과 다음 칸의 값이 같을때 dfs 재귀 수행
   • dfs메소드의 반환값을 카운트 변수에 더함
     • 재귀적으로 다음 칸을 통해 블럭의 칸 수를 누적시키기 위함
3. 카운트 값 반환

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] map;
    static int[][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int blockCnt = 0;
    static int blockSize = 0;
    public static void main(String[] args) throws IOException{
        // Please write your code here.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new int[N][N];
        for(int i = 0; i < N; i++){
            String[] line = br.readLine().split(" ");
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(line[j]);
            }
        }

        for(int i = 0; i < N;i++){
            for(int j = 0; j < N; j++){
                visited[i][j] = 1;
                int size = dfs(j, i);
                blockSize = Math.max(size, blockSize);
                if(size >= 4) {
                    blockCnt++;
                }
            }
        }

        System.out.print(String.format("%d %d", blockCnt, blockSize));
    }

    static int dfs(int x, int y){
        int cnt = 1;
        for(int i = 0; i < 4; i++){
            int newX = x + dx[i];
            int newY = y + dy[i];

            if(newX < 0 || newX >= N || newY < 0 || newY >= N ||
             visited[newY][newX] == 1 || map[newY][newX] != map[y][x])
                continue;

            visited[newY][newX] = 1;
            cnt += dfs(newX, newY);
        }

        return cnt;
    }
}