[JAVA] 백준 14500번 : 테트로미노

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

14500번: 테트로미노

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    final static int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; //변끼리 연결되어야 하므로 상하좌우 탐색만 가능
    static int N, M, max = Integer.MIN_VALUE;
    static int[][] arr;
    static boolean[][] visit;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][];
        for (int i = 0; i < N; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visit[i][j] = true;
                search(i, j, 1, arr[i][j]);
                visit[i][j] = false; //백트래킹이므로 방문 관리
            }
        }
        System.out.println(max);
    }

    private static void search(int x, int y, int cnt, int sum) {
        if(cnt == 4){
            max = Math.max(max, sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + move[i][0];
            int ny = y + move[i][1];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visit[nx][ny]) {
                if (cnt == 2) {
                    visit[nx][ny] = true;
                    search(x, y, cnt + 1, sum + arr[nx][ny]);
                    visit[nx][ny] = false;
                }
                visit[nx][ny] = true;
                search(nx, ny, cnt + 1, sum + arr[nx][ny]);
                visit[nx][ny] = false;
            }
        }
    }

}

💡 백트래킹, 구현

❗ BFS는 사용 불가능 (재귀를 활용해서 풀어야 하는 문제)
테트로미노이 도형 모양은 4칸으로 조합할 수 있는 모든 탐색의 경우의 수와 동일하다 (회전, 대칭 가능하므로)
→ 이때, 탐색은 상,하,좌,우만 가능하다 (변이 맞닿아야 하므로 대각선은 불가능)
❗ 단 예외는 "ㅗ" 모양 도형인데, 이 모양은 일련의 상하좌우 탐색으로는 불가능하다
   분기(중간)에서 양 방향으로 뻗어나가야 함
   → 이것을 위해 2번째 칸에서 (cnt = 2) 기존 탐색과 추가 탐색을 동시에 진행해 양 방향으로 뻗어나가도록 함

풀이

• 4방향 탐색 단위 정의함
• 추가 탐색의 진행 방식
  • 3번째 칸을 탐색하되, 재귀 함수의 매개변수를 2번째 칸의 위치로 줘서 그 위치에서 다시 탐색하도록 함

---

1. 블럭 모양을 보고 탐색 가능 경로와 동일함을 떠올려야 함

2. ㅗ 모양 블럭을 별도로 처리해줘야 함

    - 이 과정에서 bfs는 이용 후보에서 제외함.. 방문 관리가 어려우므로