백준 - 테트로미노

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

[문제 설명]

완전탐색 + 백트래킹 문제

 

[접근 방법]

https://girawhale.tistory.com/35

[백준] 14500번: 테트로미노 - JAVA

완전탐색과 백트래킹으로 푼다는 건 알았는데, 백트래킹 구현을 못했다.

너무 오랜만에 봐서 그런지 감이 안오더라.

결국 막판에 검색해서 다른 사람들 답안을 참고해서 풀었다.

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

public class Main {
    static int[][] map;
    static int[] directionOfRow = {-1,0,1,0};
    static int[] directionOfColumn = {0,1,0,-1};
    static boolean[][] isVisited;
    static int maxSum = Integer.MIN_VALUE;
    static int sizeOfRow;
    static int sizeOfColumn;
    public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            sizeOfRow = Integer.parseInt(st.nextToken());
            sizeOfColumn = Integer.parseInt(st.nextToken());
            map = new int[sizeOfRow][sizeOfColumn];

            for (int row = 0; row < sizeOfRow; row++) {
                st = new StringTokenizer(br.readLine()," ");
                for (int column = 0; column < sizeOfColumn; column++) {
                    map[row][column] = Integer.parseInt(st.nextToken());
                }
            }

            isVisited = new boolean[sizeOfRow][sizeOfColumn];
            for (int row = 0; row < sizeOfRow; row++) {
                for (int column = 0; column < sizeOfColumn; column++) {
                    isVisited[row][column] = true;
                    maxSum = Math.max(backtracking(row, column, map[row][column],1), maxSum);
                    isVisited[row][column] = false;
                    maxSum = Math.max(getFuckShapeSum(row, column, sizeOfRow, sizeOfColumn), maxSum);
                }
            }
            System.out.println(maxSum);

    }

    private static int backtracking(int positionOfRow, int positionOfColumn, int sum, int depth) {
        if (depth == 4) {
            return sum;
        }

        for (int idxOfDirection = 0; idxOfDirection < directionOfRow.length; idxOfDirection++) {
            int nextRowPosition = positionOfRow+directionOfRow[idxOfDirection];
            int nextColumnPosition = positionOfColumn+directionOfColumn[idxOfDirection];

            if (!checkIsInMap(nextRowPosition, nextColumnPosition, sizeOfRow, sizeOfColumn) || isVisited[nextRowPosition][nextColumnPosition]) {
                continue;
            }
            isVisited[nextRowPosition][nextColumnPosition] = true;
            maxSum = Math.max(backtracking(nextRowPosition, nextColumnPosition, sum+map[nextRowPosition][nextColumnPosition],depth+1),maxSum);
            isVisited[nextRowPosition][nextColumnPosition] = false;
        }

        return maxSum;
    }

    private static boolean checkIsInMap(int positionOfRow, int positionOfColumn, int sizeOfRow, int sizeOfColumn) {
        if ((0 <= positionOfRow && positionOfRow < sizeOfRow) && (0 <= positionOfColumn && positionOfColumn < sizeOfColumn)) {
            return true;
        }
        return false;
    }

    private static int getFuckShapeSum(int positionOfRow, int positionOfColumn, int sizeOfRow, int sizeOfColumn) {
        // 4방향을 먼저 다 더하고 차례대로 빼고 해보자
        int fiveBlockSum = map[positionOfRow][positionOfColumn];

        for (int idxOfDirection = 0; idxOfDirection < directionOfRow.length; idxOfDirection++) {
            int nextRowPosition = positionOfRow + directionOfRow[idxOfDirection];
            int nextColumnPosition = positionOfColumn + directionOfColumn[idxOfDirection];
            if (checkIsInMap(nextRowPosition, nextColumnPosition, sizeOfRow, sizeOfColumn)) {
                fiveBlockSum += map[nextRowPosition][nextColumnPosition];
            }
        }

        int answer = 0;
        for (int idxOfDirection = 0; idxOfDirection < directionOfRow.length; idxOfDirection++) {
            int currentSum = fiveBlockSum;
            int nextRowPosition = positionOfRow + directionOfRow[idxOfDirection];
            int nextColumnPosition = positionOfColumn + directionOfColumn[idxOfDirection];
            if (checkIsInMap(nextRowPosition, nextColumnPosition, sizeOfRow, sizeOfColumn)) {
                currentSum -= map[nextRowPosition][nextColumnPosition];
            }
            answer = Math.max(currentSum,answer);
        }

        return answer;
    }
}

 

이 아래 코드가 가장 핵심 같다. 방문처리하고, 후에 방문처리를 취소해야 하는.

            isVisited[nextRowPosition][nextColumnPosition] = true;
            maxSum = Math.max(backtracking(nextRowPosition, nextColumnPosition, sum+map[nextRowPosition][nextColumnPosition],depth+1),maxSum);
            isVisited[nextRowPosition][nextColumnPosition] = false;

 

완전탐색 카테고리에서 고른 문제지만, 골드가 되니까 점점 응용을 요구하는 문제가 나오는 기분이 든다.

다음에 한 번 다시 봐야할 문제 같다. + 백트래킹을 좀 풀어봐야겠다.

 

 

 

 

[내 오답]

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

public class HwangInGyu {
    static int[][] map;
    static int[] directionOfRow = {-1,0,1,0};
    static int[] directionOfColumn = {0,1,0,-1};
    static boolean[][] isVisited;
    static int maxSum = Integer.MIN_VALUE;
    static int sizeOfRow;
    static int sizeOfColumn;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        sizeOfRow = Integer.parseInt(st.nextToken());
        sizeOfColumn = Integer.parseInt(st.nextToken());
        map = new int[sizeOfRow][sizeOfColumn];

        for (int row = 0; row < sizeOfRow; row++) {
            st = new StringTokenizer(br.readLine()," ");
            for (int column = 0; column < sizeOfColumn; column++) {
                map[row][column] = Integer.parseInt(st.nextToken());
            }
        }

        for (int row = 0; row < sizeOfRow; row++) {
            for (int column = 0; column < sizeOfColumn; column++) {
                int positionOfRow = row;
                int positionOfColumn = column;
                isVisited = new boolean[sizeOfRow][sizeOfColumn];
                int sum = map[positionOfRow][positionOfColumn];
                int depth = 1;
                maxSum = Math.max(backtracking(positionOfRow, positionOfColumn, sum,depth), maxSum);
                maxSum = Math.max(getFuckShapeSum(positionOfRow, positionOfColumn, sizeOfRow, sizeOfColumn), maxSum);
            }
        }
        System.out.println(maxSum);
    }

    private static int backtracking(int positionOfRow, int positionOfColumn, int sum, int depth) {
        if (isVisited[positionOfRow][positionOfColumn]) {
            return 0;
        }
        if (depth == 4) {
            return sum;
        }
        isVisited[positionOfRow][positionOfColumn] = true;

        for (int idxOfDirection = 0; idxOfDirection < directionOfRow.length; idxOfDirection++) {
            int nextRowPosition = positionOfRow+directionOfRow[idxOfDirection];
            int nextColumnPosition = positionOfColumn+directionOfColumn[idxOfDirection];

            if (checkIsInMap(nextRowPosition, nextColumnPosition, sizeOfRow, sizeOfColumn)) {
                maxSum = Math.max(backtracking(nextRowPosition, nextColumnPosition, sum+map[nextRowPosition][nextColumnPosition],depth+1),maxSum);
                isVisited[nextRowPosition][nextColumnPosition] = true;
            }
        }

        return maxSum;
    }

    private static boolean checkIsInMap(int positionOfRow, int positionOfColumn, int sizeOfRow, int sizeOfColumn) {
        if ((0 <= positionOfRow && positionOfRow < sizeOfRow) && (0 <= positionOfColumn && positionOfColumn < sizeOfColumn)) {
            return true;
        }
        return false;
    }

    private static int getFuckShapeSum(int positionOfRow, int positionOfColumn, int sizeOfRow, int sizeOfColumn) {
        // 4방향을 먼저 다 더하고 차례대로 빼고 해보자
        int fiveBlockSum = map[positionOfRow][positionOfColumn];
        for (int idxOfDirection = 0; idxOfDirection < directionOfRow.length; idxOfDirection++) {
            int nextRowPosition = positionOfRow + directionOfRow[idxOfDirection];
            int nextColumnPosition = positionOfColumn + directionOfColumn[idxOfDirection];
            if (checkIsInMap(nextRowPosition, nextColumnPosition, sizeOfRow, sizeOfColumn)) {
                fiveBlockSum += map[nextRowPosition][nextColumnPosition];
            }
        }

        int answer = 0;
        for (int idxOfDirection = 0; idxOfDirection < directionOfRow.length; idxOfDirection++) {
            int currentSum = fiveBlockSum;
            int nextRowPosition = positionOfRow + directionOfRow[idxOfDirection];
            int nextColumnPosition = positionOfColumn + directionOfColumn[idxOfDirection];
            if (checkIsInMap(nextRowPosition, nextColumnPosition, sizeOfRow, sizeOfColumn)) {
                currentSum -= map[nextRowPosition][nextColumnPosition];
                answer = Math.max(currentSum,answer);
            }
        }

        return answer;
    }
}