백준 14500 테트로미노 Java

삼성 SW 역량테스트 기출문제인 테트로미노이다.

 

5가지의 테트로미노 중 하나를 놓았을 때 점수의 합이 최대인 경우 점수의 합을 출력하면 된다.

5가지의 테트로미노를 하나씩 놓아보면서 점수의 합이 최대일 때를 찾아내는 방법밖엔

없는 것 같았다. 

 

테트로미노의 종류가 5개인데 회전도 가능하고 대칭도 가능하기 때문에

5가지의 경우만 검사해보면 되는 것이 아니라

꽤 많은 경우를 검사해봐야 한다.

물론 이렇게 구현하면 실행 속도가 가장 빠르지만

5가지의 테트로미노의 대칭, 회전 포함 모든 경우를 다 따로 검사하는 건

너무 코드가 길 것 같아서 DFS를 통한 백트래킹으로 모든 경우를 검사해보기로 했다.

 

DFS로 상하좌우를 탐색하다가 4번째까지 탐색했을 때

그 합의 최대값을 구하는 방법으로 진행했으나

계속해서 틀렸다.

 

분명 모든 경우를 다해본 것 같았지만

DFS로 탐색했을 때 검사하지 못하는 경우가 있었다.

바로 테트로미노의 모양이 ㅗ ㅜ ㅏ ㅓ 인 경우인데

DFS를 생각해보면 이미 거쳐왔던 길을 다시 돌아갈 수 없기 때문에

저 경우에는 탐색이 불가능한 것이었다.

그래서 원래 목적이었던 짧은 코드는 조금 멀어졌지만

위의 경우는 따로 탐색을 해줬다.

+모양의 점수를 구해서

하나씩 빼주며 max값을 갱신해주는 방식으로 구현했다.

 

실행 속도는 다른 분들에 비해 엄청나게 많이 차이 났지만

비교적 코드는 짧게 구현했다.

import java.io.*;
import java.util.*;
 
public class Q14500 {
    static int n;
    static int m;
    static int[][] a;
    static int[] tx = {1, -1, 0, 0};
    static int[] ty = {0, 0, 1, -1};
    static int max = 0;
    static boolean[] visited;
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        a = new int[n][m];
        visited = new boolean[n*m];
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(reader.readLine());
            for(int j=0; j<m; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i=0; i<n*m; i++) {
            int r = i/m;
            int c = i%m;
            visited[i] = true;
            dfs(i, a[r][c], 0, visited);
            getException(i);
            Arrays.fill(visited, false);
        }
        System.out.println(max);
    }
 
    static void dfs(int idx, int sum, int cnt, boolean[] visited) {
        if(cnt==3) {
            max = Math.max(max, sum);
            return;
        }
        int r = idx/m;
        int c = idx%m;
        visited[idx] = true;
        for(int i=0; i<4; i++) {
            if(r+tx[i]>=0 && r+tx[i]<n && c+ty[i]>=0 && c+ty[i]<m) {
                if(!visited[(r+tx[i])*m+c+ty[i]]) {
                    dfs((r+tx[i])*m+c+ty[i], sum+a[r+tx[i]][c+ty[i]], cnt+1, visited);
                }
            }
        }
        visited[idx] = false;
    }
 
    static void getException(int idx) {
        int r = idx/m;
        int c= idx%m;
        int sum = a[r][c];
        int cnt = 0;
        for(int i=0; i<4; i++) {
            if(r+tx[i]>=0 && r+tx[i]<n && c+ty[i]>=0 && c+ty[i]<m) {
                sum+= a[r+tx[i]][c+ty[i]];
                cnt++;
            }
        }
        if(cnt<3 || sum < max) return;
        if(cnt==3) {
            max = Math.max(max, sum);
        } else {
            for(int i=0; i<4; i++) {
                max = Math.max(max, sum-a[r+tx[i]][c+ty[i]]);
            }
        }
    }
}