[코드트리 조별과제] 뿌요뿌요 (DFS)

뿌요뿌요 문제 링크

코드트리에서 위의 문제를 푼 과정을 기록해보도록 하겠습니다!

문제는 DFS 문제였습니다!

기본적으로 DFS 기본 문제들을 풀고 나서 학습을 진행했었습니다.
이 문제가 DFS 기본 문제들과 달랐던 점은 DFS 재귀함수를 1번 실행하는 것이 아니라
Main 함수에서 여러 번 실행한다는 점이 달랐습니다!

크게 풀이과정은 다음과 같습니다.
1. 맵 초기화
2. 돌면서 방문하지 않은 점들 DFS 실행

• DFS 시 상하좌우 인접한 곳에서 (방문되지 않은 곳 && 숫자가 같은 곳) 방문 시 블럭 크기++

3. DFS 이후에 블럭 크기를 기준으로 4 이상이면 폭탄 Cnt++
4. DFS 이후에 블럭 크기 max 갱신

이러한 과정으로 구현했습니다!
아래는 구현한 코드입니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, 1, -1, 0};

    static int bombCnt = 0;
    static int tempBlockSize = 0;
    static int maxBlockSize = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n][n];

        // 1. 맵 초기화
        for (int i = 0; i < n; i++) {
            StringTokenizer mapInput = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(mapInput.nextToken());
            }
        }
        
        // 2. 돌면서 방문하지 않은 점들 DFS 실행
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    tempBlockSize = 1;
                    dfs(i, j, map[i][j]);

                    // 3. DFS 이후에 블럭 크기를 기준으로 4 이상이면 폭탄 Cnt++
                    if (tempBlockSize >= 4) {
                        bombCnt++;
                    }

                    // 4. DFS 이후에 블럭 크기 max 갱신
                    maxBlockSize = Math.max(maxBlockSize, tempBlockSize);
                }    
            }
        }

        System.out.println(bombCnt + " " + maxBlockSize);
    }

    private static void dfs(int startX, int startY, int num) {
        for (int i = 0; i < 4; i++) {
            int cx = startX + dx[i];
            int cy = startY + dy[i];

            if (cx >= 0 && cx < n && cy >= 0 && cy < n) {
                if (!visited[cx][cy] && map[cx][cy] == num) {
                    visited[cx][cy] = true;
                    tempBlockSize++;
                    dfs(cx, cy, num);
                }
            }
        }
    }
}

DFS 실력체크 완료!