본문 바로가기
알고리즘/Brute Force

테트로-미노

by 히포파타마스 2022. 4. 22.

테트로-미노

백준 14500번 문제

https://www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

 

 

 

 

1. 문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

  • 정사각형은 서로 겹치면 안 된다.
  • 도형은 모두 연결되어 있어야 한다.
  • 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

 

[폴리오미노]

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

 

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

 

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

예제 입력 1

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

예제 출력 1

19

 

 

예제 입력 2

4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

예제 출력 2

20

 

 

예제 입력 3

4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1

예제 출력 3

7

 

 

 

 

2. 풀이

● 각 블록들을 구현한다.

● 블록들을 회전시키면서 주어진 배열에 대해 모든 경우를 계산한다(각 블록을 주어진 배열의 가능한 모든 칸에 넣어본다).

● 계산값의 최댓값을 찾는다.

 

 

 

■ 입력

[입력]

Scanner scanner = new Scanner(System.in);
int row = scanner.nextInt();
int col = scanner.nextInt();
int[][] ar = new int[row][col];

for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        ar[i][j] = scanner.nextInt();
    }
}

입력으로 오는 row, col의 정보와 각 원소 값을 받아서 배열을 만든다.

 

 

 

■ block 구현

[blocks]

ArrayList<rc[]> blocks = new ArrayList<>();

rc[] block_I = {new rc(0, 1), new rc(0, 2), new rc(0, 3)};
rc[] block_O = {new rc(0, 1), new rc(1, 1), new rc(1, 0)};
rc[] block_T = {new rc(0, 1), new rc(0, 2), new rc(-1, 1)};
rc[] block_L = {new rc(0, 1), new rc(0, 2), new rc(-1, 2)};
rc[] block_J = {new rc(0, 1), new rc(0, 2), new rc(-1, 0)};
rc[] block_S = {new rc(0, 1), new rc(-1, 1), new rc(-1, 2)};
rc[] block_Z = {new rc(0, 1), new rc(1, 1), new rc(1, 2)};

blocks.add(block_I);
blocks.add(block_O);
blocks.add(block_T);
blocks.add(block_L);
blocks.add(block_J);
blocks.add(block_S);
blocks.add(block_Z);

● 각 블럭들을 구성하는 정사각형의 위치로 블럭을 구현한다.

ex) block_ I는 일자형 블록을 의미. 일자형 블록을 눕혔을 때 가장 왼쪽의 정사각형을 기준으로 나머지 정사각형들은 각각 (0,1), (0, 2), (0,3) 만큼 떨어져서 위치해있다.

 

● 블럭들을 한꺼번에 다룰 수 있도록 모든 블록을 담을 list를 만들고 넣는다.  

 

 

[rc]

public static class rc {
    int row;
    int col;

    public rc(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

● 블럭의 정사각형의 위치를 나타내기 위한 클래스

● row와 col을 필드로 갖고 있다.

 

 

 

■ 회전, 최댓값 계산

[계산]

for (rc[] block : blocks) {
    for (int i = 0; i < 4; i++) {
        circulate(block);
        calculate(block, ar, row, col);
    }
}

System.out.println(result);

● 각 블럭들을 총 4번 회전시키다.

● 각 회전마다 주어진 배열의 가능한 모든 칸에 해당 블럭을 배치시킨다.

● 블럭이 배열의 특정 칸에 배치될 때마다 값을 계산하고 최댓값을 갱신한다.

● circulate : 블럭을 회전 시키는 메서드

● calculate : 주어진 블럭을 가능한 모든 배열의 칸에에 배치시키고 값을 계산, 최대값을 갱신하는 메서드

 

 

[circulate]

public static void circulate(rc[] block) {
    for (rc rc : block) {
        int temp_row = rc.row;
        rc.row = rc.col;
        rc.col = -temp_row;
    }
}

● 블럭을 받아 해당 블럭을 90도 회전시키는 메서드

● 좌표(a, b)를 +90도 회전시킨 위치는 (-b, a)이기 때문에 이를 그대로 구현해준다.

 

 

[calculate]

public static void calculate(rc[] block, int[][] ar, int row, int col) {
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            rc block1 = new rc(i + block[0].row, j + block[0].col);
            rc block2 = new rc(i + block[1].row, j + block[1].col);
            rc block3 = new rc(i + block[2].row, j + block[2].col);

            if (!edge(block1, row, col) || !edge(block2, row, col) || !edge(block3, row, col)) {
                continue;
            }

            int temp_result = ar[i][j] + ar[block1.row][block1.col] + ar[block2.row][block2.col]
                    + ar[block3.row][block3.col];

            if (result < temp_result) {
                result = temp_result;
            }
        }
    }
}

● 배열의 각 원소(ar[i][j])를 시작점으로 해서 주어진 블럭에 따라 나머지 3개의 정사각형의 위치를 결정한다.

● 3개의 정사각형의 위치가 주어진 배열의 범위를 넘어가면 다음 배열의 원소로 넘어간다(edge() 메서드 사용).

● 배열의 시작점이 된 원소와 3개의 정사각형 위치에  따른 값을 계산하고 계산 결과에 따라 최댓값을 담을 result의 값을 갱신한다.

 

 

[edge]

public static boolean edge(rc block, int row, int col) {
    if (block.row < 0 || block.row > row - 1 || block.col < 0 || block.col > col - 1) {
        return false;
    }
    return true;
}

블럭의 시작점이 되는 정사각형(for문의 i와 j에 값의 배열의 원소)을 제외한 나머지 3개의 정사각형이 주어진 배열의 row와 col, 0 값을 넘어가는지를 판단한다.

 

 

 

■ 전체 코드

[전체 코드]

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static int result;

    public static class rc {
        int row;
        int col;

        public rc(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public static void circulate(rc[] block) {
        for (rc rc : block) {
            int temp_row = rc.row;
            rc.row = rc.col;
            rc.col = -temp_row;
        }
    }

    public static void calculate(rc[] block, int[][] ar, int row, int col) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                rc block1 = new rc(i + block[0].row, j + block[0].col);
                rc block2 = new rc(i + block[1].row, j + block[1].col);
                rc block3 = new rc(i + block[2].row, j + block[2].col);

                if (!edge(block1, row, col) || !edge(block2, row, col) || !edge(block3, row, col)) {
                    continue;
                }

                int temp_result = ar[i][j] + ar[block1.row][block1.col] + ar[block2.row][block2.col]
                        + ar[block3.row][block3.col];

                if (result < temp_result) {
                    result = temp_result;
                }
            }
        }
    }

    public static boolean edge(rc block, int row, int col) {
        if (block.row < 0 || block.row > row - 1 || block.col < 0 || block.col > col - 1) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int row = scanner.nextInt();
        int col = scanner.nextInt();
        int[][] ar = new int[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ar[i][j] = scanner.nextInt();
            }
        }

        ArrayList<rc[]> blocks = new ArrayList<>();

        rc[] block_I = {new rc(0, 1), new rc(0, 2), new rc(0, 3)};
        rc[] block_O = {new rc(0, 1), new rc(1, 1), new rc(1, 0)};
        rc[] block_T = {new rc(0, 1), new rc(0, 2), new rc(-1, 1)};
        rc[] block_L = {new rc(0, 1), new rc(0, 2), new rc(-1, 2)};
        rc[] block_J = {new rc(0, 1), new rc(0, 2), new rc(-1, 0)};
        rc[] block_S = {new rc(0, 1), new rc(-1, 1), new rc(-1, 2)};
        rc[] block_Z = {new rc(0, 1), new rc(1, 1), new rc(1, 2)};

        blocks.add(block_I);
        blocks.add(block_O);
        blocks.add(block_T);
        blocks.add(block_L);
        blocks.add(block_J);
        blocks.add(block_S);
        blocks.add(block_Z);

        for (rc[] block : blocks) {
            for (int i = 0; i < 4; i++) {
                circulate(block);
                calculate(block, ar, row, col);
            }
        }

        System.out.println(result);
    }
}
저작자표시

댓글

티스토리툴바