[java]테트로미노 - 백준14500

문제

• 테트로미노 (백준14500)

풀이

문제 해석을 하자면,

• 5개의 테트로미노 중 하나를 사용해 제일 큰 값을 가지는 수를 출력하라

풀이

• 크게 2가지로 풀 수 있다.
  • 첫째, 총 19가지 모양을 가질 수 있으므로 하나하나 확인하는 풀이
  • 둘째, DFS 모양을 이용한 풀이
• 본인은 둘다 시도해보았고, 코드는 둘을 섞은 코드를 나타내겠다.
  • 먼저, DFS 4방향 깊이 3까지 진행하여 ‘ㅏ’,’ㅓ’,’ㅗ’,’ㅜ’ 를 제외한 모든 모양을 조회
  • 다음으로 ‘ㅏ’,’ㅓ’,’ㅗ’,’ㅜ’ 를 직접 하나하나 조회하여 확인
• 아쉽게 DFS 모양으로 깊이 3까지 진행하면 ‘ㅏ’,’ㅓ’,’ㅗ’,’ㅜ’ 를 제외한 모든 모양을 조회한다는 것을 스스로 알아내지 못했다. -> 구글링 ㅜㅜ

코드

public static int N, M, result;
public static int[][] inArr = new int[505][505];
public static boolean[][] visited = new boolean[505][505];
public static int[] dx = {0, 1, 0, -1};
public static int[] dy = {1, 0, -1, 0};

public static void dfs1(int depth, int val, int cx, int cy) {
    //base condition
    if(depth==3) {
        result = Math.max(result, val);
        return;
    }
    //recursion
    for(int i=0; i<4; i++) {
        int nx = cx+dx[i];
        int ny = cy+dy[i];
        if(nx<0||ny<0||nx>=N||ny>=M) continue;
        if(visited[nx][ny]) continue;
        visited[nx][ny] = true; // 갔던 좌표 다시 안가기 위함
        dfs1(depth+1, val+inArr[nx][ny], nx, ny);
        visited[nx][ny] = false; // 백트래킹
    }
}


public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    //init
    for(int i=0; i<N; i++ ) {
        for (int j=0; j<M; j++) {
            inArr[i][j] = 0;
            visited[i][j] = false;
            result = 0;
        }
    }
    //input
    for(int i=0; i<N; i++ ) {
        stk = new StringTokenizer(br.readLine(), " ");
        for (int j=0; j<M; j++) {
            inArr[i][j] = Integer.parseInt(stk.nextToken());
        }
    }
    //run
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            visited[i][j] = true;
            dfs1(0, inArr[i][j], i, j);
            visited[i][j] = false;

            // 'ㅜ,ㅗ,ㅏ,ㅓ' 추가 처리
            if (i - 1 >= 0 && j - 1 >= 0 && i + 1 <= N - 1) // 'ㅓ'
                result = Math.max(result, inArr[i - 1][j] + inArr[i][j] + inArr[i][j - 1] + inArr[i + 1][j]);
            if (i - 1 >= 0 && j + 1 <= M-1 && i + 1 <= N - 1) // 'ㅏ'
                result = Math.max(result, inArr[i - 1][j] + inArr[i][j] + inArr[i][j + 1] + inArr[i + 1][j]);
            if (i - 1 >= 0 && j - 1 >= 0 && j + 1 <= M - 1) // 'ㅗ'
                result = Math.max(result, inArr[i - 1][j] + inArr[i][j] + inArr[i][j - 1] + inArr[i][j+1]);
            if (j - 1 >= 0 && j + 1 <= M-1 && i + 1 <= N - 1) // 'ㅜ'
                result = Math.max(result, inArr[i][j-1] + inArr[i][j] + inArr[i+1][j] + inArr[i][j+1]);
        }
    }
    //output
    System.out.println(result);
}

느낀점

생략