[코드트리 챌린지] 블로그 챌린지 : 4회차(9월27일 ~ 10월 2일) / 뿌요뿌요

블로그 챌린지 처음 시작하게 된 이유도 이렇게라도 강제로 알고리즘 공부를 하기 위해서이다.

---

import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int[][] box;
    static boolean[][] visited;
    static int maxBombCnt = 1;
    static int bombCnt;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        box = new int[N][N];

        StringTokenizer st;
        for(int i = 0; i < N ; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N ; j++){
                box[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int allBombGroupCnt = 0;
        visited = new boolean[N][N];
        for(int i = 0; i < N; i++){
            for(int j = 0 ; j < N ; j++){
                bombCnt = 0;
                if(visited[i][j]){continue;}
                dfs(i,j,box[i][j]);
                if(bombCnt>=4){
                    maxBombCnt = Math.max(maxBombCnt, bombCnt);
                    allBombGroupCnt+=1;

                }
            }
        }
       
        System.out.println(allBombGroupCnt+" "+maxBombCnt);
    }
    static int[][] way = {{-1,0},{0,1},{1,0},{0,-1}};
    private static void dfs(int x, int y, int startValue){
        visited[x][y] = true;
        bombCnt += 1;

        for(int w = 0; w < 4; w++){
            int nx = x + way[w][0];
            int ny = y + way[w][1];
            if(nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny])continue;
            if(box[nx][ny]== startValue){
                dfs(nx,ny,startValue);
            }
        }
    }
}

자주 놓치는 부분이

 

(1) dfs 처음 진입할 때,

visited check를 하지않아서 bombCnt 수를 잘못 체크하는 경우

(2) dfs 내에서 다음 위치를 선택할 때,

- 현재 값이랑 같은 값인지 확인하는 로직을 안 넣는 경우

- 방문여부를 체크하지 않는 경우

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

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