[백준] 14500번 테트로미노 - Java, 자바

난이도

골드 5

문제

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

풀이

1. 도형을 (1,1)부터 (N,M) 까지 모두 탐색하며 해당 점에서 만들 수 있는 테트로미노를 구한다.

     for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visit[i][j] = true;
                tetromino(i, j, 1, map[i][j]);
                visit[i][j] = false;
                check(i,j);
            }
        }

2. 백트래킹을 사용하여 정사각형 4개를 선택하며 도형에 있는 수의 합을 구한다.
   그리고 그 수가 최대인 값을 구한다.

    public static void tetromino(int x, int y, int depth, int sum) {
        if (depth == 4) {
            max = Math.max(sum, max);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (!visit[nx][ny]) {
                    visit[nx][ny] = true;
                    tetromino(nx, ny, depth + 1, sum + map[nx][ny]);
                    visit[nx][ny] = false;
                }
            }
        }
    }

3. 위의 처리만 해준다면 주어진 도형 중에 핑크색으로 되어있는 도형을 처리할 수 없다.
   

핑크색 도형을 처리하기 위해 check라는 함수를 하나 만들었다.
핑크색 도형에서 나올 수 있는 경우의 수 4가지(ㅜ,ㅗ,ㅓ,ㅏ)를 직접 구했다.

    static void check(int x, int y) {
//        0과 m, n 사이
        if (x + 1 < n && y + 2 < m)
            max = Math.max(max, map[x][y] + map[x][y + 1] + map[x + 1][y + 1] + map[x][y + 2]);
        if (x - 1 >= 0 && y + 2 < m)
            max = Math.max(max, map[x][y] + map[x][y + 1] + map[x - 1][y + 1] + map[x][y + 2]);
        if (x + 2 < n && y + 1 < m)
            max = Math.max(max, map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y + 1]);
        if (x + 2 < n && y - 1 >= 0)
            max = Math.max(max, map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y - 1]);
    }

코드

package 삼성SW역량테스트기출문제;

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

public class BOJ14500 {
    static int n, m;
    static int[][] map;
    static boolean[][] visit;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[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());
            }
        }

        visit = new boolean[n][m];

        // 구현
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visit[i][j] = true;
                tetromino(i, j, 1, map[i][j]);
                visit[i][j] = false;
                check(i,j);
            }
        }

        System.out.println(max);
    }

    public static void tetromino(int x, int y, int depth, int sum) {
        if (depth == 4) {
            max = Math.max(sum, max);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (!visit[nx][ny]) {
                    visit[nx][ny] = true;
                    tetromino(nx, ny, depth + 1, sum + map[nx][ny]);
                    visit[nx][ny] = false;
                }
            }
        }
    }



    static void check(int x, int y) {
//        0과 m, n 사이
        if (x + 1 < n && y + 2 < m)
            max = Math.max(max, map[x][y] + map[x][y + 1] + map[x + 1][y + 1] + map[x][y + 2]);
        if (x - 1 >= 0 && y + 2 < m)
            max = Math.max(max, map[x][y] + map[x][y + 1] + map[x - 1][y + 1] + map[x][y + 2]);
        if (x + 2 < n && y + 1 < m)
            max = Math.max(max, map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y + 1]);
        if (x + 2 < n && y - 1 >= 0)
            max = Math.max(max, map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y - 1]);
    }
}