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

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

14500번: 테트로미노

문제

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

정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

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

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

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

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

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

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

접근방법

 테트로미노로 구할 수 있는 값 중 가장 큰 값을 구하는 것이 목표이다. 큰 값을 구하기 위해 테트로미노가 갖고 있는 특징들을 이해해야 한다. 특징을 생각해보고 풀이로 넘어가자.

풀이

 테트로미노는 모두 4개의 폴리오미노로 구성되어 있다. 즉, 해당 문제는 도형에 맞는 4칸 중 가장 큰 값을 구하라는 문제가 된다. 이 부분에서 노드 4개 중 가장 큰 값을 탐색하는 문제구 나라 고인식 하는 것이 중요하다. 탐색의 문제임을 인지했다면, 해당 도형들로 탐색하기 위해 어떤 모양을 지니고 있는지 확인해볼 필요가 있다. 

 

한 폴리도미노를 기준으로 '┤' 블록을 제외한다면 다음과 같이 나타낼 수 있다.

 

한 폴리오미노에서 방향을 돌렸을 때, 나타나는 모든 테트로미노는 다음과 같이 표현된다. 이를 합쳐보면 다음과 같은 그림으로 나타낼 수 있다. 

https://velog.io/@skyepodium/ 님의 경우의수 그림

( 너무 못 그려서 타 블로거님의 그림을 빌려왔다.) 흰 부분을 포함하여 모두 4칸씩 갔을 때, 갈 수 있는 범위이다. 감이 혹시 오는가?   '┤' 제외한 4가지 도형들의 모든 경우의 수는 흰 부분에서 4칸을 뻗어나갈 수 있는 모든 경우의 수를 의미하는 것이다. 즉, 문제는 '깊이가 4인 노드 중에 노드합이 가장 큰 곳은 어디니?'라고 묻는 것이다. 이 부분을 해결하기 위해 DFS를 적용한다. 이유는 다음과 같다.

 

1. 도형의 모양대로 결과 값이 나와야 한다. 즉, 하나의 도형의 결과값을 구한 뒤, 다른 도형과 비교해야 하므로, 리프 노드까지 우선적으로 탐색하여 '테트로미노'를 만드는 것이 우선이다.

 

2. Undo가 되야한다. 도형을 만들기 위해 이미 들렸던 곳도 다른 노드를 통해 들를 수 있어야 한다. BFS로는 불가능하다. 

 

테트로미노의 유형이 깊이가 4인 모든 테트로미노의 경우의 수를 보증하게 되므로, 전제 탐색 후 최대 값만 구하면 된다.

 

잠깐! 그럼  '┤' 도형도 처리해야지?

  '┤' 도형을 따로 놔둔 이유를 이제는 알 것이다. DFS 탐색으로는 해당 도형을 처리할 수 없다. 해당 도형은 동시에 여러 군데를 접근해야 하기 때문에 DFS 알고리즘을 통해서는 구현하기가 어렵다. 따라서 따로 케이스를 두고 처리한다. 

 

dfs 결괏값과  '┤' 도형으로 구할 수 있는 값 중 최댓값을 반환해주면 문제는 해결된다.

 

코드

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

public class Main {

    int[][] ways = {{1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}};

    //중앙을 중심으로
    int[][][] special_case = {{{-1,0},{1,0},{0,1}}, /* ├  */
            {{0,-1},{0,1},{1,0}},/* ┬ */
            {{0,-1},{-1,0},{1,0}},/* ┤ */
            {{0,-1},{-1,0},{0,1}}}; /* ┴ */
    boolean[][] visited ;

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");

        int row = Integer.parseInt(stk.nextToken());
        int col = Integer.parseInt(stk.nextToken());

        int[][] arr = new int[row][col];
        visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            stk = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < col; j++) {
                arr[i][j] = Integer.parseInt(stk.nextToken());
            }
        }


        int result = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                result = Math.max(result, solution(arr, i, j));
            }
        }

        System.out.println(result);
    }

    private int solution(int[][] arr, int x, int y) {

		//dfs로 4가지 테트로미노 처리 
        visited[x][y] = true;
        int result = dfs(arr, x, y, 0, visited);
        visited[x][y] = false;

		//특수 케이스에 대해 결과값 처리 
        for (int[][] ways : special_case){
            int val = arr[x][y] ;
            boolean toggle = false;
            for (int[] way : ways){
                int next_x = x + way[0];
                int next_y = y + way[1];
                if (next_x >= 0 && next_x < arr.length && next_y >= 0 && next_y < arr[0].length){
                    val +=arr[next_x][next_y];
                }else{
                    toggle = true;
                    break;
                }
            }
            //하나라도 안되면 다음 모양으로 전환
            if(toggle)
                continue;

            result = Math.max(result,val);
        }

        return result;
    }

    private int dfs(int[][] arr, int x, int y, int depths, boolean[][] visited) {

        int res = 0;
        if (depths == 3) {
            return arr[x][y];
        }

        for (int i = 0; i < ways.length; i++) {
            int next_x = x + ways[i][0];
            int next_y = y + ways[i][1];

			//범위안
            if (next_x >= 0 && next_x < arr.length && next_y >= 0 && next_y < arr[0].length) {
					//미방문
                if (!visited[next_x][next_y]) {

                    visited[next_x][next_y] = true;
                    res = Math.max(res, dfs(arr, next_x, next_y, depths + 1, visited));
                    visited[next_x][next_y] = false;
                }

            }

        }

        return arr[x][y] + res;
    }
}

결과

 

 

 드디어 Lv 3 Clear!! 해당 문제를 처음 풀 때, 시간 초과가 걸렸는데, 아무래도 dfs를 사용함에 있어 파라미터를 과도하게 넣은 듯한 감이 있어, 전역 변수로 올리고, visited 변수의 재사용성을 조금 높였다.(이전 코드에서는 dfs 시작마다, visitied을 새로 생성해서 썼는데, 이 부분을 줄이고 통과했다.)  

 

 

 

Reference)

이미지 - https://velog.io/@skyepodium/%EB% B0% B1% EC% A4%80-14500-%ED%85% 8C% ED% 8A% B8% EB% A1% 9C% EB% AF% B8% EB%85% B8

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.