BOJ#14500 테트로미노

BOJ#14500 테트로미노

* 문제

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

* 풀이

2017년 상반기 삼성전자 SW 역량테스트 기출 문제입니다.

테트로미노에서 dfs로 탐색 가능한 블록이 있고, 탐색 불가능한 블록(ㅓ, ㅗ, ㅜ, ㅏ)이 있습니다.

즉, dfs로 탐색 + (ㅓ,ㅗ,ㅜ,ㅏ)에 대해 탐색을 하면 답을 얻을 수 있습니다.

(ㅓ,ㅗ,ㅜ,ㅏ) 탐색 아이디어는 다음과 같습니다.

현재 위치가 (row, col)일 때

(row, col)값과 (row, col)에서 상,하,좌,우 4방향 값을 모두 더해줍니다. 그리고 4방향 값에서 최소 값을 다시 빼줍니다.

= 현재 위치 값 + 4방향 sum - 4방향 값 중 최소값

즉 플러스 + 모양에서 4방향 중 가장 최소값을 빼면 (ㅓ,ㅗ,ㅜ,ㅏ)의 가장 큰 경우가 구해지는 것!

위 아이디어는 아래 블로그에서 참고하였습니다. 👍

http://jason9319.tistory.com/239

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%2314500_Tetromino/src/Main.java

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

/**
 * BOJ#14500 테트로미노
 * https://www.acmicpc.net/problem/14500
 */

public class Main {

    static final int[] dRow = {0, -1, 0, 1};
    static final int[] dCol = {-1, 0, 1, 0};
    static final int LIMIT = 4;
    static final int INF = 100000000;

    static int N, M;
    static int[][] map = new int[501][501];
    static boolean[][] visited = new boolean[501][501];

    static int maxValue = 0;

    public static void main(String[] args) throws IOException {

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        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());
            }
        }

        // solve
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {

                // 1. dfs로 탐색 가능한 테트로미노
                dfs(0, i, j, 0);

                // 2. dfs로 탐색 불가능한 테트로미노
                solve(i, j);
            }
        }

        System.out.println(maxValue);
    }

    static void dfs(int depth, int row, int col, int sum) {

        if (depth == LIMIT - 1) {

            sum += map[row][col];

            maxValue = maxValue < sum ? sum : maxValue;
            return;
        }

        visited[row][col] = true;

        for (int i = 0; i < 4; i++) {

            int nextRow = row + dRow[i];
            int nextCol = col + dCol[i];

            if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) continue;
            if (visited[nextRow][nextCol]) continue;

            dfs(depth + 1, nextRow, nextCol, sum + map[row][col]);
        }

        visited[row][col] = false;
    }

    static void solve(int row, int col) {

        int[] adjValue = {-1, -1, -1, -1};

        int nInvalidity = 0;
        int minValue = INF;
        int sum = 0;
        for (int i = 0; i < 4; i++) {

            int nextRow = row + dRow[i];
            int nextCol = col + dCol[i];

            if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) {

                nInvalidity++;
                continue;
            }

            adjValue[i] = map[nextRow][nextCol];

            minValue = minValue > adjValue[i] ? adjValue[i] : minValue;
            sum += adjValue[i];
        }

        int ret = 0;
        if (nInvalidity >= 2) {

            return;
        } else if (nInvalidity == 1) {

            ret = sum + map[row][col];
        } else if (nInvalidity == 0) {

            ret = sum + map[row][col] - minValue;
        }

        maxValue = maxValue < ret ? ret : maxValue;
    }
}