[BOJ] 백준 [14500] 테트로미노 JAVA

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

📝문제

📝풀이

테트리스 블록을 암거나 하나 놓았을 때 그 블록이 위치한 격자 점수 합의 최대값을 구하는 문제이다.

어느 한 점 x,y 에서 시작해서 깊이 우선탐색 DFS를 돌리면 블록 모양이 나온다.
그런데 T 블록은 DFS로 구할 수 없으니 , 그 구간만 BFS로 구해야한다.

BFS를 진행할 때 만약 4방향 모두 진행 할 수 있다면
중심좌표 x,y 의 값 + (4방향 좌표의 합) = sum 이라고 하면
sum - ( 4방향 각 좌표) 가 T 블록 점수 다른모양 4개가 나온다.

만약 4방향 모두 진행 못하고 3방향으로만 가능하면 블록은 1개이다.

import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    static int w, h,max=0;
    static int[][] map;
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        h = input[0]; w = input[1];
        map = new int[h][w];
        visit = new boolean[h][w];
        for(int i=0;i<h;i++){
             map[i] = stream(br.readLine().split(" "))
                      .mapToInt(Integer::parseInt).toArray();
        } // end input

        for(int y=0;y<h;y++){
            for(int x=0;x<w;x++){
                visit[y][x] = true;
                dfs(x,y,1,map[y][x]); // 블록들 탐색
                bfs(x,y); // t 블록 탐색
                visit[y][x] = false;
            }
        }

        System.out.println(max);
    }

    static int[] dx={0,0,1,-1},dy={1,-1,0,0};
    private static void dfs(int x, int y, int depth, int sum) {

        if(depth==4){
            max = Math.max(max,sum);
            return;
        }

        for(int dir=0;dir<dx.length;dir++){
            int nextX = dx[dir]+x;
            int nextY = dy[dir]+y;

            if(!isRange(nextX,nextY) || visit[nextY][nextX])
                continue;

            visit[nextY][nextX]=true;
            dfs(nextX,nextY,depth+1,sum+map[nextY][nextX]);
            visit[nextY][nextX]=false;
        }

    }

    private static void bfs(int x, int y) {

        int sum = map[y][x];
        LinkedList<Integer> tBlocks = new LinkedList<>();

        for(int dir=0;dir<dx.length;dir++){
            int nextX = dx[dir]+x;
            int nextY = dy[dir]+y;

            if(!isRange(nextX,nextY))
                continue;

            tBlocks.add(map[nextY][nextX]);
            sum+=map[nextY][nextX];
        }

        if(tBlocks.size()==4){ // 4방향 모두 가능 한 경우
            for (Integer t : tBlocks)
                max = Math.max(max,sum-t);
        }else if(tBlocks.size()==3){ // 하나만 있는 경우
            max = Math.max(max,sum);
        }

    }

    private static boolean isRange(int x,int y){
        return x>=0&&y>=0&&x<w&&y<h;
    }
}