BJ G5 14500 테트로미노

BJ G5 14500 테트로미노

 

 

문제링크

http://www.youtu.be/rXdmuDf9WS0

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=rXdmuDf9WS0

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

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

/**
 * @author itsmeyjc
 * @since 2020. 5. 11.
 * @see https://www.acmicpc.net/problem/14500
 * @mem 33636
 * @time 568
 * @caution #dfs, #bruteforce
 */
public class BJ_G5_14500_테트로미노 {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int maxSum;

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));

        StringTokenizer tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken()); // (4 ≤ N, M ≤ 500)
        M = Integer.parseInt(tokens.nextToken());

        map = new int[N][M];
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 0; c < M; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }

        visited = new boolean[N][M];

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                visited[r][c] = true;
                // 'ㅜ'를 제외한 나머지 경우는 DFS로 탐색해보기
                dfs(r, c, 1, map[r][c]);
                // 'ㅜ'는 별도로 처리
                maxSum = Math.max(getLast(r, c), maxSum);
                visited[r][c] = false;
            }
        }
        System.out.println(maxSum);
    }

    static void dfs(int row, int col, int cnt, int sum) {
        if (cnt == 4) {
            maxSum = Math.max(maxSum, sum);
            return;
        }

        for (int d = 0; d < dirs.length; d++) {
            int nr = row + dirs[d][0];
            int nc = col + dirs[d][1];

            if (isIn(nr, nc) && !visited[nr][nc]) {
                visited[nr][nc] = true;
                dfs(nr, nc, cnt + 1, sum + map[nr][nc]);
                visited[nr][nc] = false;
            }
        }
    }

    static int getLast(int row, int col) {
        int base = map[row][col];
        int cnt = 0;// 사방 탐색 성공 회수
        int min = Integer.MAX_VALUE;// 탐색 과정에서 발견한 최소 값
        // 중심점을 중심으로 사방 탐색
        for (int d = 0; d < dirs.length; d++) {
            int nr = row + dirs[d][0];
            int nc = col + dirs[d][1];
            if (isIn(nr, nc)) {
                cnt++;
                base += map[nr][nc];
                min = Math.min(min, map[nr][nc]);
            }
        }
        // 4방 탐색이 4군데 다 성공했다면 최소값을 빼주기 - 이게 그나마 최대값
        if (cnt == 4) {
            return base - min;
        }
        // 3 방향만 성공했으면 그대로 진행
        else if (cnt == 3) {
            return base;
        }
        // 나머지경우는 모양 만들기 실패
        else {
            return -1;
        }
    }

    static boolean isIn(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < M;
    }

    private static String src = "5 5\r\n" +
                                "1 2 3 4 5\r\n" +
                                "5 4 3 2 1\r\n" +
                                "2 3 4 5 6\r\n" +
                                "6 5 4 3 2\r\n" +
                                "1 2 1 2 1";
}