📝문제

도형들이 테트리스의 형태인 것을 이용하여 그래프 탐색에서 많이 쓰이는 dfs + Backtracking으로 풀 수 있을 것이라 생각했다. 하지만 단순히 이 방법만 생각한다면 나처럼 예제3번에서 예제출력과 다른 출력값이 나올 것이다. 단순이 dfs로 푼다면 ㅓ ㅏ ㅗ ㅜ 모양은 고려하지 못한 것!

왜냐하면 "ㅜ" 모양이 회전한 형태는 다른 테트로미노와 달리 그래프 탐색의 두번째 칸에서 2개의 도형이 다른 방향으로 한 칸씩 증가한 형태이기 때문이다.

그래서 나는 이 모양을 검사하는 코드를 구현하여 기존의 dfs 코드에 추가했다.

코드가 좀 난잡하고 중복되는 부분이 많은데, 따로 함수로 정의하고 call하면 더 많은 시간과 메모리가 소요되어서 그냥 이대로 제출했다.

그리고 실제 코테에 이 문제가 나오면 이렇게 코드를 작성할 것 같다.

📌코드

package BruteForce;

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

public class BOJ14500 {

  /**
   * dfs로 풀어보자 : 각 칸으로 돌면서 1. 밑 노드로 2. 옆 노드로
   * 포인터 이동 방향을 두가지로 제한했을 때는 L을 시계/반시계 방향으로 90도만큼 회전한 도형에 대해 탐색 못함
   */

  static int n,m;
  static int[][] map;
  static int answer = 0;
  static int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  static boolean[][] visited;
  static int[][] ecp1 = {{0, -1, 0, 1}, {0, -1, 1, 0}, {0, 1, 1, 0}};
  static int[][] ecp2 = {{1, 0, 0, 1}, {-1, 0, 1, 0}, {-1, 0, 0, 1}};

  static void dfs(int sr, int sc, int r, int c, int cnt, int sum){

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

    for(int i = 0; i < 4; i++){
      int nr = r + move[i][0];
      int nc = c + move[i][1];
      if(0 <= nr && nr < n && 0 <= nc && nc < m && !visited[nr][nc]){
        visited[nr][nc] = true;
        dfs(sr, sc, nr, nc, cnt+1, sum+map[nr][nc]);
        visited[nr][nc] = false;
      }
    }


    // shape : ㅜ ㅏ ㅗ ㅓ
    if(cnt == 2){
      if(r-sr == 1 && c-sc == 0){
        for(int i = 0; i < 3; i++){
          int nr1 = r + ecp1[i][0];
          if(nr1 < 0 || nr1 >= n) continue;
          int nc1 = c + ecp1[i][1];
          if(nc1 < 0 || nc1 >= m) continue;
          int nr2 = r + ecp1[i][2];
          if(nr2 < 0 || nr2 >= n) continue;
          int nc2 = c + ecp1[i][3];
          if(nc2 < 0 || nc2 >= m) continue;
          answer = Math.max(answer, sum + map[nr1][nc1] + map[nr2][nc2]);
        }
      }
      else if(r-sr == 0 && c-sc == 1){
        for(int i = 0; i < 3; i++){
          int nr1 = r + ecp2[i][0];
          if(nr1 < 0 || nr1 >= n) continue;
          int nc1 = c + ecp2[i][1];
          if(nc1 < 0 || nc1 >= m) continue;
          int nr2 = r + ecp2[i][2];
          if(nr2 < 0 || nr2 >= n) continue;
          int nc2 = c + ecp2[i][3];
          if(nc2 < 0 || nc2 >= m) continue;
          answer = Math.max(answer, sum + map[nr1][nc1] + map[nr2][nc2]);
        }
      }
    }
  }

  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()); // row
    m = Integer.parseInt(st.nextToken()); // col
    map = new int[n][m];
    visited = new boolean[n][m];
    for(int i = 0; i < n; i++){
      st = new StringTokenizer(br.readLine());
      for(int j = 0; j < m; j++){
        map[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
        visited[i][j] = true;
        dfs(i, j, i, j, 1, map[i][j]);
        visited[i][j] = false;
      }
    }
    System.out.println(answer);
  }
}