[백준] 테트로미노

문제

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

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다

풀이

주의 테트로미노 원소 한개(정사각형 4칸) 의 합의 최댓값을 구하시오

문제를 잘못 해석해서 한 개의 테트로미노에 쓰여진 숫자의 합의 최댓값인데. 겹치치 않게 모든 칸에 배치를 한 다음 숫자의 합의 최댓값으로 해석을 해서 초반에 애를 먹었다.
처음에 각 테트로미노의 경우의 수 9가지를 배열로 모두 담아 풀라고했는데 그것보다 더 나은 풀이법을 찾아서 글을 쓴다.

풀이는 다음과 같다.

• dfs, dx,dy 배열을 사용해 4개의 원소를 탐색해 최댓값을 구한다.
• 단, ㅓ, ㅏ, ㅗ, ㅜ 모양은 위와 같은 방법으로 탐색이 불가능함으로 같은 좌표 [i,j] 에서 탐색하는 것을 따로 만들어 준다.

코드

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

class Main {
    static boolean[][] visited;
    static int[][] map;
    static int max;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];
        max = 0;

        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, map[i][j], 0);
                visited[i][j] = false;
                //ㅓ, ㅏ , ㅗ , ㅜ 예외처리. 인접한 4칸 중 3칸 고르기
                excepts(i,j,0,0,map[i][j]);
            }
        }
        System.out.println(max);
    }

    public static void dfs(int x, int y, int sum, int cnt) {
//에러. 4로 했었음 ㅇㅇ
        if (cnt >= 3) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;

            if (nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length || visited[nx][ny])
                continue;
            visited[nx][ny] = true;
            dfs(nx, ny, sum + map[nx][ny], cnt + 1);
            visited[nx][ny] = false;
        }
    }

    public static void excepts(int x, int y, int start, int cnt, int sum) {
        if (cnt >= 3) {
            max = Math.max(max, sum);
            return;
        }
        for (int d = start; d < 4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];
//start 부터 시작함으로 visit 배열 필요없음
            if (nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length)
                continue;
            excepts(x,y,d+1,cnt+1,sum+map[nx][ny]);
        }
    }
}