[코드트리/INTERMEDIATE LOW] 뿌요뿌요 (JAVA)

📖 문제

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

 

 

💡  풀이 방식

• DFS

격자 위의 모든 점을 탐색하며 방문하지 않은 점에서 dfs를 실행한다.

- 해당 칸에서 4방향 탐색을 통해 블럭을 이루고 있는 칸 수(currBlockNum)를 계산한다.

- 계산한 블럭을 이루는 칸 수가 4개 이상이라면, 터지는 블럭 수(bombCnt)에 1을 더한다.

- 그리고 현재 계산한 블럭을 이루는 칸 수와 여태껏 최대 블럭 크기를 비교해 최대 블럭 크기를 둘 중 더 큰 값으로 갱신한다.

 

 

💥 유의사항

격자에서 다음 방향으로 이동할 수 있는 조건

1) 격자 범위 내에 있어야 한다.

2) 방문한 적 없어야 한다.

3) 현재 칸의 값과 같아야 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    static int N;
 
    static int[][] grid;
    static boolean[][] visited;
 
    static int bombCnt = 0;   // 터지는 블럭 수
    static int max = 0;       // 최대 블럭 크기
 
    static int currBlockNum;    // 블럭 수
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        grid = new int[N][N];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        visited = new boolean[N][N];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(!visited[i][j]) {
                    currBlockNum = 1;
                    dfs(i, j);
 
                    if(currBlockNum >= 4) {
                        bombCnt++;
                    }
                    max = Math.max(max, currBlockNum);
                }
            }
        }
 
        System.out.println(bombCnt + " " + max);
    }
 
    private static void dfs(int x, int y) {
        visited[x][y] = true;
 
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if(!inRange(nx, ny) || visited[nx][ny] || grid[nx][ny] != grid[x][y])    continue;
            
            currBlockNum++;
            dfs(nx, ny);
        }
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N);
    }
}

 

 

---

💦 어려웠던 점

- 저 currBlockNum 부분을 dfs 메소드에 인자로 넣어서 어떻게 해보려고 했는데 잘 되지 않았다,, 그냥 편하게 static 변수인 currBlockNum 따로 만들어서 갱신하고 활용하는 것으로...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리