[backjoon]14500 테트로미노 java

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

14500번: 테트로미노

돌린 배열을 바탕으로 다 확인해야하는데 이게 어떻게 Gold5밖에 안 되는지 처음엔 말이 안 된다고 생각했는데, 가만 보면 금방 풀 수 있다.

폴리오미노라는 도형들을 보면 공통적으로 4개임을 알 수 있다. 또한, ㅜ 모양을 제외하고는 한 점에서 중복되지 않고 3번 더 갔을 때의 경로들임을 아는 것이 문제의 포인트!

즉, ㅜ 모양을 제외하고는 모든 모양이 4방향으로 갈 수 있는 모든 경로임을 알 수 있다.

따라서 모든 지점을 중복되지 않게 모두 확인해가면서 제일 큰 값을 구해주면 된다.

ㅜ모양은 한 점을 기준으로 될 수 있는 모든 방향 ㅜ/ㅗ/ㅓ/ㅏ의 방향들을 기록하고 순서대로 방문해서 계산할 수 있는 값들을 더하는 방식으로 풀이!

BFS를 이용하면 전체 방문이 불가능하고! 최대 map의 값이 500, 길이가 4를 확인했을 때 DFS를 통해 값을 구할 수 있다.

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M, answer;
    static int[][] map;
    static int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    static boolean[][] marked;
 
    public static void main(String[] args) throws Exception {
        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];
        answer = 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++) {
            marked = new boolean[N][M];
            for (int j = 0; j < M; j++) {
                marked[i][j] = true;
                dfs(i, j, 1, map[i][j]);
                unique(i, j);
            }
        }
        System.out.println(answer);
    }
    
    //<< 특이한 모양은 값을 방향들을 구해줘서 풀이해준다. -> 경우의 수가 크지 않기에 다 탐색해도 됨.>>
    public static void unique(int row, int col) {
        int[][][] dirs = { { { 1, -1 }, { 1, 0 }, { 1, 1 } }, // ㅗ
                { { 1, 0 }, { 1, 1 }, { 2, 0 } }, // ㅏ
                { { 0, -1 }, { 0, 1 }, { 1, 0 } }, // ㅜ
                { { 1, 0 }, { 1, -1 }, { 2, 0 } } // ㅓ
        };
        for (int turn = 0; turn < 4; turn++) {
            int sum = map[row][col];
            for (int d = 0; d < 3; d++) {
                int nextR = row + dirs[turn][d][0];
                int nextC = col + dirs[turn][d][1];
                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M)
                    break;
                sum += map[nextR][nextC];
            }
            answer = Math.max(sum, answer);
        }
    }
 
    //<< 길이가 4인 것들만 모아서 최대 거리 확인하기>>
    public static void dfs(int row, int col, int length, int sum) {
        if (length == 4) {
            answer = Math.max(sum, answer);
            return;
        }
 
        for (int d = 0; d < 4; d++) {
            int nextR = row + dirs[d][0];
            int nextC = col + dirs[d][1];
            if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M)
                continue;
            if (marked[nextR][nextC])
                continue;
            marked[nextR][nextC] = true;
            dfs(nextR, nextC, length + 1, sum + map[nextR][nextC]);
            marked[nextR][nextC] = false;
        }
    }
}

 

풀이 중에 느닷없이 시간초과에 걸렸었는데 방문 확인하는 배열을 시작 값이 움직일 때마다 초기화해줘서 그랬다.

초기화를 쉽게 하지 말자.