문제 바로가기

나의 풀이

삼성 SW 역량 테스트 문제에 좋은 구현 문제들이 많다고 해서 풀기로 마음먹고 풀어본 첫 문제이다. 확실히 구현을 대비를 안했던 만큼 어려웠고 결국 다른 사람들의 풀이를 조금은 참고해서 풀이를 할 수 있었다.

나도 처음에 문제를 봤을 때, 빡 구현을 해야할 지 혹은 dfs를 이용해서 풀어야할 지 고민하는데 시간을 너무 오래 쓴 것 같다. 실제로 dfs를 사용하지 않고, 모든 폴리오미노를 회전, 대칭시킨 경우의 수를 모두 구현하여 풀이를 한 분도 계셨다. 앞으로 구현 문제를 일주일에 1~2개는 풀면서 빨리 문제를 풀기 위해 정확한 판단과 신속한 결정을 내릴 수 있도록 실력을 길러야겠다.

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

class Main {

    static int[][] map;
    static int dx[] = {0,0,1,-1}, dy[] = {1, -1, 0, 0};
    static int row, col, max;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        map = new int[row][col];
        visited = new boolean[row][col];
        max = 0;

        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                /*
                * 다른 사람들의 풀이에서는 map[i][j] 대신 0을 넣고 depth를 4까지 돌려서 
                * 시작점을 제외하고 4칸을 더하는 식으로 계산한듯 하다
                * 나는 뭔가 시작점도 더해주고 시작하고 싶어서 백트래킹을 사용하였다
                 */
                visited[i][j] = true;
                dfs(i,j,0, map[i][j]);
                visited[i][j] = false;
                exception(i,j);
            }
        }

        System.out.println(max);
    }

    // 'ㅗ' 모양 제외한 나머지 폴리노미오를 dfs로 탐색. depth가 3이 되면 return하여 4칸의 합의 최댓값을 구한다
    static void dfs(int x, int y, int depth, int count) {
        if (depth == 3) {
            max = Math.max(count, max);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= row || ny >= col) continue;
            if (visited[nx][ny]) continue;
            visited[nx][ny] = true;
            // depth를 1 늘리고, 다음 칸의 값을 더한재로 재귀를 돌린다
            dfs(nx, ny, depth + 1, count + map[nx][ny]);
            visited[nx][ny] = false;
        }
    }

    /*
     'ㅗ' 의 회전 모양 4가지를 게산해주는 함수이다
     일단 '+' 모양을 만드는 것을 목표로 하는데, 범위가 벗어났을 때는 wing 값을 하나씩 빼준다
     'ㅗ' 모양이 되려면 wing이 3개는 있어야 하므로 2개 이하가 되면 continue해주고
     '+' 모양이 완성될 경우에는 4개의 날개중에 가장 작은 값을 제거해준다
     */
    static void exception(int x, int y) {
        int wing = 4;
        int min = Integer.MAX_VALUE;
        int sum = map[x][y];
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (wing <= 2) return;
            if (nx < 0 || ny < 0 || nx >= row || ny >= col) {
                wing--;
                continue;
            }
            min = Math.min(min, map[nx][ny]);
            sum += map[nx][ny];
        }
        if (wing == 4) {
            sum -= min;
        }
        max = Math.max(max, sum);
    }
}