[백준] 14500번 테트로미노

[CMSSKKK]

TITLE

테트로미노

LINK

• 문제 출처 사이트 : 백준
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

풀이 언어

• java

코드

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

public class Main {

    private static int n;
    private static int m;
    private static int[][] board;
    private static boolean[][] visit;
    private static int[] dx = {0,0,-1,1};
    private static int[] dy = {-1,1,0,0};
    private static int max = 0;

    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());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visit[i][j] = true;
                dfs(i, j, 0, 0);
                visit[i][j] = false;
            }
        }

        System.out.println(max);

    }

    private static void dfs(int x, int y, int depth, int sum) {

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


        if (depth == 0) {
            int[] temp = new int[4];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                    continue;
                }
                temp[i] = board[nx][ny];
            }

            check(temp, board[x][y]);
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                continue;
            }
            if (!visit[nx][ny]) {
                visit[nx][ny] = true;
                dfs(nx, ny, depth + 1, sum + board[x][y]);
                visit[nx][ny] = false;
            }

        }
    }

    private static void check(int[] arr, int start) {

        for (int i = 0; i < 4; i++) {
            int sum = start;
            for (int j = 0; j < 4; j++) {
                if(j != i) {
                   sum += arr[j];
                }
            }
            max = Math.max(sum, max);
        }

    }
}

핵심 로직 혹은 자료구조

• ㅗ ㅓ ㅏ ㅜ 이녀석을 어떻게 처리할것인가하는 조건이 추가 된 dfs 브루트포스

시간 복잡도

• O( )