이것저것 개발 블로그

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

풀이)

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

public class Main_BJ_14500_테트로미노 {
    static int[][] map;
    static int max, n, m;
    static int[] dx = {-1, 1, 0 ,0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer 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());
            }
        }

        boolean[][] visited = new boolean[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                visited[i][j] = true;
                dfs(i, j, 0, 0, visited);
                visited[i][j] = false;
                shape(i, j);
            }
        }

        System.out.println(max);

    }//main
    private static void dfs(int x, int y, int cnt, int sum, boolean[][] visited){
        if(cnt == 4) {
            max = Math.max(max, sum);
            return;
        }

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(check(nx, ny) && !visited[nx][ny]){
                visited[nx][ny] = true;
                dfs(nx, ny, cnt+1, sum+map[x][y], visited);
                visited[nx][ny] = false;
            }
        }
    }//dfs

    private static boolean check(int x, int y){
        if(x<0 || y<0 || x>=n || y>=m)
            return false;
        return true;
    }//check

    private static void shape(int x, int y){
        if(x<n-2 && y<m-1)
            max = Math.max(max, map[x][y]+map[x+1][y]+map[x+2][y]+map[x+1][y+1]);

        if(x<n-2 && y>0)
            max = Math.max(max, map[x][y]+map[x+1][y]+map[x+2][y]+map[x+1][y-1]);

        if(x>0 && y<m-2)
            max = Math.max(max, map[x][y]+map[x][y+1]+map[x][y+2]+map[x-1][y+1]);

        if(x<n-1 && y<m-2)
            max = Math.max(max, map[x][y]+map[x][y+1]+map[x][y+2]+map[x+1][y+1]);

    }//shape
}

시간초과 때문에 조금 힘들었다.

1. ㅗ 모양을 제외하고는 dfs로 구하기 간단해서 구했다.

2. ㅗ 모양을 구하기 위해 shape이라는 함수를 따로 만들어서 구현해줬다.(x, y 기준으로 범위를 넘지 않게끔 잡아준 후 더하면 된다)

하지만 시간초과..

찾아보니 전역변수를 많이 설정해도 참조하는데 시간이 오래 걸리기 때문에 지역변수로 바꾸려고 했다.

따라서 boolean[][] 함수를 지역변수로 만들었지만, 탐색할때마다 생성하게 했더니,, 그것도 시간이 오래 걸려서..(생각해보면 당연함)

dfs 돌리기 전 후로 true, false 값을 바꿔주는 것으로 변경했다!!

좀 더 생각해보면 좋았을텐데 아쉬운 문제였다.