[DFS/자바] 코드트리 IL. 뿌요뿌요

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

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

 

코드트리 Intermediate Low 단계의 BFS 유형을 모두 푼 김에, DFS의 테스트 문제를 다시 한번 풀어보았다. 오랜만에 푸니까 조금 헤맸지만 그래도 풀어냈음에 의의를 가지고 싶다.

 

문제 해석

이 문제는 BFS로도 풀 수 있을 것 같은데, 핵심은 그래프 알고리즘으로 푼다는 것이다. 인접한 칸을 하나의 블록으로 인지하는 것이고, 이어진 칸들을 하나의 블록으로 계산하며 그 크기를 파악하는 것이 관건이다.

 

우선, 블록의 최대 크기를 priority queue로 구하려고 했다. n이 1부터 100까지이므로 최소 블록 크기가 1일 것이므로 pq에 -1부터 추가해 주었다.

 

그리고 dfs를 돌리면서 depth++ 를 수행하면서 해당 블록의 크기를 측정하였다. 이 depth는 그리드로 움직이는 로직이기 때문에 전역 변수로 선언하여 하나의 블록의 크기를 전부 돌때까지 누적되도록 하여 크기를 가늠할 수 있도록 하였다. 이후 dfs가 한번 다 돌면 depth의 크기를 통해 해당 블록이 터질 블록인지 아닌지를 검사한 뒤에 boomCnt++를 수행한 뒤 depth를 1로 초기화한다.

 

이러한 매커니즘으로 최대 depth는 pq에서 poll 하고, 터지는 블록의 개수는 boomCnt를 출력하도록 하였다.

 

풀이 코드

package 코드트리.그래프.DFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class 뿌요뿌요_2nd {
    private static int n;
    private static int[][] arr;
    private static boolean[][] visited;
    private static int[][] dist;
    private static Queue<Integer> pq = new PriorityQueue<>();
    private static int depth = 1;


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

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int boomCnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = true;
                pq.add(-1);
                dfs(new Pair(i, j));
                if (depth >= 4) {
                    boomCnt++;
                }
                depth = 1;
            }
        }
        System.out.println(boomCnt + " " + -pq.poll());
    }
    private static void dfs(Pair crt) {
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        for (int i = 0; i < 4; i++) {
            int newY = crt.y + dy[i];
            int newX = crt.x + dx[i];
            if (canGo(newY, newX, arr[crt.y][crt.x])) {
                visited[newY][newX] = true;
                dist[newY][newX] = dist[crt.y][crt.x] + 1;
                depth++;
                dfs(new Pair(newY, newX));
                pq.add(-depth);
            }
        }
    }

    private static class Pair {
        private int x, y;

        private Pair(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }


    private static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < n;
    }

    private static boolean canGo(int y, int x, int num) {
        return inRange(y,x) && arr[y][x] == num && !visited[y][x];
    }
}