[백준 14500번] 테트로미노 - java

문제 설명

1. 4개 정사각형을 이어붙이는 도형들이 있다. (변을 붙이는 모든 형태)

2. 지도가 주어진다.

3. 위의 도형으로 숫자를 더해서 최대값을 구하면 된다.

풀이 과정

1. 구현

2. 삼전 문제는 매번 느끼는건데 뭔가 구현 위주로 코드를 길게 만드는걸 선호하는 것 같다. 개인적으로 취향은 아님

3. DFS + 엣지케이스 처리.

4. depth 4 까지 찾아가면서 DFS 해주면 되고, ㅓ ㅏ ㅗ ㅜ 같은 중간에 가지가 뻗어나가는것은 이로 처리하기가 쉽지 않다(뒤로 돌아와서 check를 다시 해야하기 때문) 이는 그냥 따로 엣지케이스로 처리해준다.

5. 성능이 될까? 했는데 이게 되네..

코드

import java.util.*;

public class Main {
  private static int[][] map;
  private static boolean[][] check;
  private static int[] xMove = {-1, 1, 0, 0};
  private static int[] yMove = {0, 0, -1, 1};
  private static int ans = 0;
  private static int N, M;
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    N = sc.nextInt();
    M = sc.nextInt();
    map = new int[N][M];
    check = new boolean[N][M];
    
    for(int i=0; i<N; i++) {
      for(int j=0; j<M; j++) {
        map[i][j] = sc.nextInt();
      }
    }
    
    for(int i=0; i<N; i++) {
      for(int j=0; j<M; j++) {
        dfs(i, j, 1, 0);
        exceptShape(i, j);
      }
    }
    
    System.out.println(ans);
  }
  
  private static void dfs(int x, int y, int depth, int sum) {
    if(x >= N || y >= M || x < 0 || y < 0 || check[x][y]) return;
    check[x][y] = true;
    sum+=map[x][y];
    
    if(depth == 4) {
      ans = Math.max(ans, sum);
      check[x][y] = false;
      return;
    }
    
    for(int i=0; i<4; i++) {
      int xTo = x + xMove[i];
      int yTo = y + yMove[i];
      dfs(xTo, yTo, depth+1, sum);
    }
    check[x][y] = false;
  }
  
  private static void exceptShape(int x, int y) {
      // ㅗ 모양
      if (x > 0 && y > 0 && y < M - 1) {
          int sum = map[x][y] + map[x - 1][y] + map[x][y - 1] + map[x][y + 1];
          ans = Math.max(ans, sum);
      }
      // ㅜ 모양
      if (x < N - 1 && y > 0 && y < M - 1) {
          int sum = map[x][y] + map[x + 1][y] + map[x][y - 1] + map[x][y + 1];
          ans = Math.max(ans, sum);
      }
      // ㅓ 모양
      if (y > 0 && x > 0 && x < N - 1) {
          int sum = map[x][y] + map[x - 1][y] + map[x + 1][y] + map[x][y - 1];
          ans = Math.max(ans, sum);
      }
      // ㅏ 모양
      if (y < M - 1 && x > 0 && x < N - 1) {
          int sum = map[x][y] + map[x - 1][y] + map[x + 1][y] + map[x][y + 1];
          ans = Math.max(ans, sum);
      }
  }
}