[ 백준 ] 14500 테트로미노

codesver·2022년 12월 20일
0

Baekjoon

목록 보기
51/72
post-thumbnail

Analyze

테트로미노는 5가지의 도형이 있다.

첫 번째 도형은 다음과 같다.

하나의 블럭을 기준으로 잡았을 때 다음과 같이 4가지의 경우가 나온다.

두 번째 도형은 다음과 같다.

하나의 블럭을 기준으로 잡았을 때 다음과 같이 4가지의 경우가 나온다.

세 번째 도형은 다음과 같다.

하나의 블럭을 기준으로 잡았을 때 다음과 같이 8가지의 경우가 나온다.

네 번째 도형은 다음과 같다.

하나의 블럭을 기준으로 잡았을 때 다음과 같이 8 가지의 경우가 나온다.

5번째 도형은 다른 방법으로 다루기 때문에 잠시 후에 다룬다.

위의 4가지 도형을 하나의 중심 블럭을 잡고 생각하면 다음과 같은 영역을 만들 수 있다.

즉, 하나의 블럭에서 DFS으로 백트래킹 탐색을 하여 최대 4개의 칸을 탐색하면 된다.

다음은 현재 탐색한 1번 블럭을 기준으로 1, 2, 3, 4번 도형을 탐색하는 방법이다.

5번 블럭은 DFS로 탐색이 불가능한 도형이다.

5번 블러의 가운데 블럭을 기준으로 회전하면 총 5개의 블럭이 채워진다.

구하고자하는 값은 최댓값이다.

5개의 칸을 모두 더하고 4방향의 칸 중 가장 작은 값을 빼면 최댓값을 구할 수 있다.

Solution

private static int[][] paper;
private static boolean[][] visited;
private static int max = Integer.MIN_VALUE;

↪ paper는 테트로미노를 놓을 수 있는 종이이다.
↪ visited는 탐색 과정에서 같은 위치를 중복 탐색하지 않게 방지하는 것이다.
↪ max는 테트로미노가 놓인 위치의 숫자합 최대값이다.


private static void solution() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int row = Integer.parseInt(tokenizer.nextToken());
    int col = Integer.parseInt(tokenizer.nextToken());

    initialize(row, col);
    search(row, col);
    result.append(max);
}
private static void initialize(int row, int col) throws IOException {
    StringTokenizer tokenizer;
    paper = new int[row + 2][col + 2];
    visited = new boolean[row + 2][col + 2];
    for (int r = 1; r <= row; r++) {
        tokenizer = new StringTokenizer(reader.readLine());
        for (int c = 1; c <= col; c++) 
        paper[r][c] = Integer.parseInt(tokenizer.nextToken());
    }
}

↪ 탐색을 할 때 현재 위치의 4방향을 탐색하기 때문에 끝에 여백을 두어 초기화한다.


private static void search(int row, int col) {
    for (int r = 1; r <= row; r++) {
        for (int c = 1; c <= col; c++) {
            visited[r][c] = true;
            dfs(r, c, 1, paper[r][c]);
            visited[r][c] = false;
            max = Math.max(max, specialSearch(r, c));
        }
    }
}

↪ DFS를 통해 탐색을 하나 백트래킹으로 탐색할 것이다.
↪ 탐색하기 전에 현재 탐색 예정지를 방문 표시하고 탐색한다.
↪ 탐색을 하고 나왔을 때는 방문 기록을 제거한다.


private static void dfs(int row, int col, int depth, int sum) {
    if (depth == 4) max = Math.max(max, sum);
    else {
        deeper(row - 1, col, depth + 1, sum);
        deeper(row, col + 1, depth + 1, sum);
        deeper(row + 1, col, depth + 1, sum);
        deeper(row, col - 1, depth + 1, sum);
    }
}

↪ 탐색한 위치가 4번째 위치였을 때는 max를 업데이트하고 백트래킹한다.
↪ 추가 탐색은 4방향(UP, RIGHT, DOWN, LEFT)으로 한다.


private static void deeper(int row, int col, int depth, int sum) {
    if (!visited[row][col] && paper[row][col] != 0) {
        visited[row][col] = true;
        dfs(row, col, depth, sum + paper[row][col]);
        visited[row][col] = false;
    }
}

↪ 이미 방문을 한 곳이거나 종이를 벗어났으면 탐색을 하지 않는다.
↪ 이전과 마찬가지로 탐색전에 방문 기록 이후 기록 삭제한다.


private static int specialSearch(int row, int col) {
    int up = paper[row - 1][col];
    int right = paper[row][col + 1];
    int down = paper[row + 1][col];
    int left = paper[row][col - 1];
    return paper[row][col] + up + right + down + left 
                - Math.min(Math.min(up, down), Math.min(right, left));
}

↪ ⫟ 모양의 테트로미노를 탐색한다.
↪ 가운데와 4방향을 모두 더한다.
↪ 최댓값을 구하는 것이기 때문에 4방향 중 최솟값을 감산한 것이 최댓값이다.

profile
Hello, Devs!

0개의 댓글