문제

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

Gold IV

코드 (Java)

import java.util.Scanner;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //metadata
        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine();

        //map info
        map = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                map[i][j] = sc.nextInt();
            }
            sc.nextLine();
        }

        int max = 0;

        //solve with recursive dfs + edge case
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                int res = search(i, j, 1, 0);
                int res2 = tcase(i, j);
                if (max < res) max = res;
                if (max < res2) max = res2;
            }
        }

        //print result
        System.out.print(max);
    }

    static int search(int i, int j, int cnt, int score) {
        //System.out.printf("%d %d %d %d\n", i, j, cnt, score);
        int cur_val = map[i][j];
        int max = score + cur_val;
        int res;
        visited[i][j] = true;

        if (cnt >= 4) {
            visited[i][j] = false;
            return max;
        }
        if (i > 0 && !visited[i-1][j]) {
            res = search(i-1, j, cnt+1, score + cur_val);
            if (res > max) max = res;
        }
        if (i < N-1 && !visited[i+1][j]) {
            res = search(i+1, j, cnt+1, score + cur_val);
            if (res > max) max = res;
        }
        if (j > 0 && !visited[i][j-1]) {
            res = search(i, j-1, cnt+1, score + cur_val);
            if (res > max) max = res;
        }
        if (j < M-1 && !visited[i][j+1]) {
            res = search(i, j+1, cnt+1, score + cur_val);
            if (res > max) max = res;
        }

        visited[i][j] = false;

        return max;

    }

    //since tetronomino with shape T can't be covered with DFS, we use special function to check this case.
    static int tcase(int i, int j) {
        int max = 0;
        int res;

        //tip at bottom
        if (i > 0 && i < N-1 && j < M - 1) {
            res = map[i-1][j] + map[i][j] + map[i+1][j] + map[i][j+1];
            if (max < res) max = res;
        }
        //tip at right
        if (j > 0 && j < M-1 && i < N - 1) {
            res = map[i][j] + map[i+1][j] + map[i][j-1] + map[i][j+1];
            if (max < res) max = res;
        }

        //tip at left
        if (j > 0 && j < M-1 && i > 0) {
            res = map[i][j] + map[i-1][j] + map[i][j-1] + map[i][j+1];
            if (max < res) max = res;
        }

        //tip at top
        if (i > 0 && i < N-1 && j > 0) {
            res = map[i-1][j] + map[i][j] + map[i+1][j] + map[i][j-1];
            if (max < res) max = res;
        }

        return max;
    }
}

풀이

졸면서 짜서 잘 짠건진 솔직히 모르겠다

브루트 포스. 크기가 작아서 감당 가능.

처음에 별생각없이 BFS로 시도 -> 실패 (반례 존재, 이상하게 구현하기도 했다.)

4 5
5 5 5 5 5
5 100 1 1 100
5 5 5 5 5
5 5 5 5 5

이후 별생각없이 DFS로 시도 -> 실패 (재귀적으로 구현했는데 T모양 테트로노미노 탐색을 못함)

그래서 별도로 T 테트로노미노를 해결하는 함수도 따로 만들었다.

속도가 많이 느려서, 슬슬 스캐너를 버려야 하나 고민중.

BFS 짜다보니 PriorityQueue를 Java에서 어떻게 다루는지 조금 더 알게 되었다는 것은 안비밀

아무리 졸면서 짰다지만 구현 능력 좀 길러야 할 것 같다.