[BOJ/Java] 14500. 테트로미노

[BOJ/Java] 14500. 테트로미노

14500번: 테트로미노

---

문제 해석

이 문제에서는 격자 위에 다양한 형태의 테트로미노를 놓았을 때 얻을 수 있는 점수의 최댓값을 찾는 문제다. 테트로미노는 모두 4개의 칸으로 구성되어 있고, 격자의 값에 따라 점수가 정해진다. 테트로미노는 90도 회전이나 대칭이 가능하다.

풀이 과정

Java 코드는 DFS(깊이 우선 탐색)를 사용하여 격자에서 가능한 모든 테트로미노의 위치를 탐색하고, 그 중 최댓값을 찾는다. 각 테트로미노는 최대 4개의 칸으로 구성되므로, DFS를 통해 4번까지 탐색을 진행한다.

 

1. 입력 처리: 격자의 크기와 격자의 값들을 입력받는다.
2. DFS 탐색: 격자의 모든 위치에서 DFS를 시작한다. 각 위치에서 시작할 때마다 방문 배열을 사용하여 이미 방문한 위치를 표시하고, DFS로 가능한 모든 모양을 만들어 최대합을 찾는다.
3. 특별한 모양 처리: 테트로미노 중 'ㅗ' 모양은 DFS의 기본적인 4방향 연속 탐색으로는 만들 수 없으므로 별도의 처리가 필요하다. 이 코드에서는 이 모양을 고려하지 않고 있는 것으로 보인다.
4. 결과 출력: 계산된 최대 점수를 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No14500;

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static int N; // 격자의 행 크기
    private static int M; // 격자의 열 크기
    private static int[][] map; // 격자 데이터
    private static boolean[][] v; // 방문 표시 배열
    private static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 이동 방향 벡터
    private static int ans; // 최대 점수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for (int x = 0; x < N; x++) {
            st = new StringTokenizer(br.readLine());
            for (int y = 0; y < M; y++) {
                map[x][y] = Integer.parseInt(st.nextToken());
            }
        }
        sol();
        sb.append(ans);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void sol() {
        ans = 0;
        v = new boolean[N][M];

        for (int x = 0; x < N; x++) {
            for (int y = 0; y < M; y++) {
                v[x][y] = true;
                dfs(x, y, 1, map[x][y]);
                v[x][y] = false;
            }
        }
    }

    private static void dfs(int x, int y, int depth, int s) {
        if (depth == 4) {
            ans = Math.max(ans, s);
            return;
        }

        for (int[] d : direction) {
            int nx = x + d[0];
            int ny = y + d[1];

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (v[nx][ny]) continue;

            if (depth == 2) {
                v[nx][ny] = true;
                dfs(x, y, depth + 1, s + map[nx][ny]); // 재귀적으로 다음 위치 탐색
                v[nx][ny] = false;
            }

            v[nx][ny] = true;
            dfs(nx, ny, depth + 1, s + map[nx][ny]);
            v[nx][ny] = false;
        }
    }
}

시간 복잡도 분석

시간 복잡도는 𝑂(𝑁×𝑀×44)로, 격자의 모든 위치에서 최대 4번의 이동을 고려하기 때문에 계산된다.

느낀점

이 문제는 다양한 테트로미노 모양을 고려하면서 가능한 모든 경우의 수를 탐색하는 복잡한 문제이다. DFS를 통해 이러한 탐색 문제를 효과적으로 해결할 수 있는 방법을 실습할 수 있었다. 또한, 시뮬레이션과 조합 문제에 대한 이해를 깊이 있게 다루는 좋은 경험이었다.