[2024.10.31(목)] 코드트리 : DFS/뿌요뿌요

 

3문제 다 풀어서 뿌듯하당!

 

https://www.codetree.ai/missions/2/problems/puyo-puyo/submissions

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

 

난이도

• 중
• 이것도 어제 배운 개념 알면 쉽게 풀 수 있음

 

배운점 & 실수한 점

• findBlock 돌리고 blockNum을 초기화 해줘야 했는데 빼먹어서 답이 이상해졌음

 

 

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

public class Main {

    static int n;
    static int[][] grid;
    static boolean[][] visited;

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    
    static int maxBlockNum = 0;
    static int totalBlockNum = 0;
    static int blockNum = 0;

    public static void findBlock(int r, int c){
        if(isBlock(r, c)){
            visited[r][c] = true;
            blockNum++;

            for(int i = 0; i<4; i++){
                int new_r = r+dr[i];
                int new_c = c+dc[i];
                if(isBlock(new_r, new_c) && isSame(new_r, new_c, grid[r][c])){
                    findBlock(new_r, new_c);
                }
            }
        }
    }

    public static boolean isRange(int r, int c){
        return (r>=0 && r<n && c>=0 && c<n);
    }

    public static boolean isBlock(int r, int c){
        if(!isRange(r, c) || visited[r][c]) return false;
        return true;
    }

    public static boolean isSame(int r, int c, int num){
        return (num == grid[r][c]);
    }

    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];
        visited = new boolean[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());
            }
        }

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(!visited[i][j]){
                    findBlock(i, j);
                    if(blockNum>maxBlockNum) maxBlockNum = blockNum;
                    if(blockNum>=4) totalBlockNum++;
                    blockNum = 0;
                }
            }
        }

        System.out.println(totalBlockNum+" "+maxBlockNum);
    }
}