문제

테트로미노 - 골드 5

---

문제 이해

• 상,하,좌,우를 탐색하면서 테트로미노를 만든다. -> BFS or DFS(선택)
• 종이의 0,0 부터 N-1,M-1 까지 탐색하면서 최대값을 구한다.
• 예외 상황(ㅏ, ㅓ, ㅜ, ㅗ)의 경우 따로 처리한다.

---

코드

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

public class BaekJoon_14500 {
  static int result;
  static int[][] board;
  static int[][] isVisited;
  static int N;
  static int M;
  static int[] moveR = { -1, 1, 0, 0 };
  static int[] moveC = { 0, 0, -1, 1 };

  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];
    isVisited = new int[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++) {
        isVisited[i][j] = 1;
        dfs(i, j, 0, board[i][j]);
        isVisited[i][j] = 0;
        check(i, j);
      }
    }

    System.out.println(result);
  }

  public static void dfs(int r, int c, int depth, int value) {
    if (depth == 3) {
      result = Math.max(result, value);
      return;
    }

    for (int i = 0; i < 4; i++) {
      int currentR = r + moveR[i];
      int currentC = c + moveC[i];

      if (0 <= currentR && currentR < N && 0 <= currentC && currentC < M && isVisited[currentR][currentC] == 0) {
        isVisited[currentR][currentC] = 1;

        dfs(currentR, currentC, depth + 1, value + board[currentR][currentC]);
        isVisited[currentR][currentC] = 0;
      }
    }
  }

  static void check(int r, int c) {
    // 시작점 왼쪽 위 상단
    if (r < N - 2 && c < M - 1) // ㅏ
      result = Math.max(result, board[r][c] + board[r + 1][c] + board[r + 2][c] + board[r + 1][c + 1]);

    if (r < N - 2 && c > 0) // ㅓ
      result = Math.max(result, board[r][c] + board[r + 1][c] + board[r + 2][c] + board[r + 1][c - 1]);

    if (r < N - 1 && c < M - 2) // ㅜ
      result = Math.max(result, board[r][c] + board[r][c + 1] + board[r][c + 2] + board[r + 1][c + 1]);

    if (r > 0 && c < M - 2) // ㅗ
      result = Math.max(result, board[r][c] + board[r][c + 1] + board[r][c + 2] + board[r - 1][c + 1]);
  }
}

---

코드 설명

DFS를 통해 테트로미노를 만들기 위해서는 0 depth부터 시작해서 3 depth 가 되면 테트로미노를 만들게 된다. 이때 파라미터 값으로 누적된 합을 넘겨주고 이 값을 static 변수로 선언한 result와 비교해서 최대값을 업데이트 해준다.

예외 상황의 경우에는 좌표값을 직접 넣어줘서 해당 합과 결과값을 비교하면 된다.

• 예외 상황
  

---