[백준] 테트로미노 : 14500 : Java - 구현 (G4)

1. 문제

14500번: 테트로미노

• 테트로미노는 정사각형 4개를 이어 붙인 도형이다. 5개 뿐이다.
• 주어진 테트로미노를 대칭, 회전 시켜도 된다.
• 하나의 테트로미노를 놓을 때 얻을 수 있는 최대 수들의 합을 구한다.

---

 

 

2. 어떻게 풀까

결국에 모든 테트로미노를 하나씩 놓아서 구해야한다. 하지만 도형의 회전을 어떻게 구현해야할까?

회전에 따른 규칙을 찾아 이용하고자 했는데, 도저히 규칙을 찾을 수가 없었다! 그래서 우선 풀고봐야하니 

변수에다 도형 정보들을 대칭 빼고 다 하드 코딩으로 박았다.. ㅎㅎ 

// 도형 정보
    static int [][][] ternomino1 = {{{1,1,1,1}},
            {{1},{1},{1},{1}}};
    static int [][][] ternomino2 = {{{1,1}, {1,1}}};
    static int [][][] ternomino3 = {{{1,0}, {1,0}, {1,1}},
            {{1,1,1},{1,0,0}},
            {{1,1},{0,1},{0,1}},
            {{0,0,1},{1,1,1}}};
    static int [][][] ternomino4 = {{{1,0}, {1,1}, {0,1}} , {{0,1,1},{1,1,0}}};
    static int [][][] ternomino5 = {{{1,1,1}, {0,1,0}},
            {{0,1},{1,1},{0,1}},
            {{0,1,0},{1,1,1}},
            {{1,0},{1,1},{1,0}}};

 

도형들의 정보가 다 있으니, 이제 맵에 하나하나 적용시키면서 온 맵을 돌아다니며 얻을 수 있는 최대값을 찾는다.

	{
	// 생략
    for(int i=0; i< ternomino1.length; i++){
                getMax(ternomino1[i]);
            }
            for(int i=0; i< ternomino2.length; i++){
                getMax(ternomino2[i]);
            }
            for(int i=0; i< ternomino3.length; i++){
                getMax(ternomino3[i]);
                getMax(symmetry(ternomino3[i]));
            }
            for(int i=0; i< ternomino4.length; i++){
                getMax(ternomino4[i]);
                getMax(symmetry(ternomino4[i]));
            }
            for(int i=0; i< ternomino5.length; i++){
                getMax(ternomino5[i]);
                getMax(symmetry(ternomino5[i]));
            }
	// 생략        
	}
        
    public static void getMax(int [][] ternomino){
        ArrayList<Point> points = new ArrayList<>();
        for(int i=0; i<ternomino.length; i++){
            for(int j=0; j<ternomino[0].length; j++){
                if(ternomino[i][j] == 1)
                    points.add(new Point(i,j));
            }
        }

        for(int i=0; i< map.length; i++){
            for(int j=0; j<map[0].length; j++){
                int sum = 0;
                for(Point p : points){
                    if(p.row +i >= map.length || p.col+j >=map[0].length){
                        sum = 0;break;
                    }
                    sum += map[p.row+i][p.col+j];
                  
                }
                max = Math.max(max, sum);
            }
        }
    }

 

도형들의 대칭 도형을 구하는 것은 쉽다. 바로 (x, y) -> (x, 세로 길이-1 -y) 식을 대칭을 할 때 적용시키면 된다. 

public static int[][] symmetry(int [][] ternomino){
        int [][] newTernomino;
        newTernomino = new int[ternomino.length][ternomino[0].length];

        for(int i=0;i <ternomino.length; i++){
            for(int j=0; j<ternomino[0].length; j++){
                newTernomino[i][j] = ternomino[i][ternomino[0].length-1-j];
            }
        }
        return newTernomino;
    }

 

 

3. 다른 좋은 방법

나는 도형의 정보가 있을 때 회전 시키는 방법을 도저히 모르겠어서 하나하나 다 박았놓았지만, 방법은 물론 있다! 

바로 다음과 같은 규칙이다 (출처 : https://redbinalgorithm.tistory.com/585)

JAVA : 배열 회전, 배열 90도 회전 방법

 

또한 이 문제는 대부분 DFS로 푸는 문제이다. 왜냐하면 주어진 5개의 테트로미노는 정사각형 4개를 이어붙일 때 만들 수 있는 모든 경우의 도형이다. 그러므로 DFS 탐색을 진행하며 깊이가 4일 때 얻을 수 있는 수들의 합을 체크해주면 된다! 하지만 마지막 도형인 아래 도형은 DFS로 구할 수 없다. 갑자기 가운데에서 틔어나가기 때문이다. 그러므로 아래 도형에 대해서는 하드코딩으로 구현하는 방법을 사용한다.(참고 : https://girawhale.tistory.com/35)

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

 

 

4. 전체 코드

전체 코드는 다음과 같다.

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    // 도형 정보
    static int [][][] ternomino1 = {{{1,1,1,1}},
            {{1},{1},{1},{1}}};
    static int [][][] ternomino2 = {{{1,1}, {1,1}}};
    static int [][][] ternomino3 = {{{1,0}, {1,0}, {1,1}},
            {{1,1,1},{1,0,0}},
            {{1,1},{0,1},{0,1}},
            {{0,0,1},{1,1,1}}};
    static int [][][] ternomino4 = {{{1,0}, {1,1}, {0,1}} , {{0,1,1},{1,1,0}}};
    static int [][][] ternomino5 = {{{1,1,1}, {0,1,0}},
            {{0,1},{1,1},{0,1}},
            {{0,1,0},{1,1,1}},
            {{1,0},{1,1},{1,0}}};

    static  int [][] map;
    static int max = Integer.MIN_VALUE;


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());
        map = new int[row][col];

        // map 점수 입력
        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< ternomino1.length; i++){
            getMax(ternomino1[i]);
        }
        for(int i=0; i< ternomino2.length; i++){
            getMax(ternomino2[i]);
        }
        for(int i=0; i< ternomino3.length; i++){
            getMax(ternomino3[i]);
            getMax(symmetry(ternomino3[i]));
        }
        for(int i=0; i< ternomino4.length; i++){
            getMax(ternomino4[i]);
            getMax(symmetry(ternomino4[i]));
        }
        for(int i=0; i< ternomino5.length; i++){
            getMax(ternomino5[i]);
            getMax(symmetry(ternomino5[i]));
        }
        bw.write(max + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void getMax(int [][] ternomino){
        ArrayList<Point> points = new ArrayList<>();
        for(int i=0; i<ternomino.length; i++){
            for(int j=0; j<ternomino[0].length; j++){
                if(ternomino[i][j] == 1)
                    points.add(new Point(i,j));
            }
        }

        for(int i=0; i< map.length; i++){
            for(int j=0; j<map[0].length; j++){
                int sum = 0;
                for(Point p : points){
                    if(p.row +i >= map.length || p.col+j >=map[0].length){
                        sum = 0;break;
                    }
                    sum += map[p.row+i][p.col+j];
                    if(sum == 25){
                        int d =0;
                    }
                }
                max = Math.max(max, sum);
            }
        }
    }
    public static int[][] symmetry(int [][] ternomino){
        int [][] newTernomino;
        newTernomino = new int[ternomino.length][ternomino[0].length];

        for(int i=0;i <ternomino.length; i++){
            for(int j=0; j<ternomino[0].length; j++){
                newTernomino[i][j] = ternomino[i][ternomino[0].length-1-j];
            }
        }
        return newTernomino;
    }
}

class Point{
    int row;
    int col;
    Point(int row, int col){
        this.row = row;
        this.col = col;
    }
}