Yoo Chaewon

Yoo Chaewon

신나고 재밌게🤪

[ALGORITHM]BOJ14500-테트로미노

문제

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

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

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

img

아름이는 크기가 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

나의 코드

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

public class Main {
    static int[][] map;
    static int max = 0;
    static int N;
    static int M;

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(input.nextToken());
        M = Integer.parseInt(input.nextToken());
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            StringTokenizer str = new StringTokenizer(bufferedReader.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(str.nextToken());
            }
        }

        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = true;
                Find(visited, j, i, 1, map[i][j]);
                visited[i][j] = false;
                max = Math.max(max, ExceptionShape(j, i));
            }
        }
        System.out.println(max);
    }

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void Find(boolean[][] visited, int x, int y, int depth, int sum) {
        if (depth == 4) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N || visited[nextY][nextX]) continue;
            visited[nextY][nextX] = true;
            Find(visited, nextX, nextY, depth + 1, sum + map[nextY][nextX]);
            visited[nextY][nextX] = false;
        }
    }

    public static int ExceptionShape(int x, int y) {
        int size = 1;
        int sum = map[y][x];
        int minValue = Integer.MAX_VALUE;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N ) continue;
            size++;
            sum += map[nextY][nextX];
            minValue = Math.min(minValue, map[nextY][nextX]);
        }

        if (size == 4) return sum;
        else if (size == 5) return sum - minValue;
        else return 0;
    }
}

  • 이어져있는 4개를 찾으면 되니까 DFS로 우선 탐색을 했다.

    static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void Find(boolean[][] visited, int x, int y, int depth, int sum) {
  if (depth == 4) {//4칸이 되면 지금까지 4칸 더한 값을 비교했다.
    max = Math.max(max, sum);
    return;//4칸 더 이상 볼필요 없으므로 return ~
  }
    
  for (int i = 0; i < 4; i++) {
    int nextX = x + dx[i];
    int nextY = y + dy[i];
      
    if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N || visited[nextY][nextX]) continue;
    visited[nextY][nextX] = true;
    Find(visited, nextX, nextY, depth + 1, sum + map[nextY][nextX]);
    visited[nextY][nextX] = false;
  }
}

    그냥 4칸을 탐색하는 방식이다 !

  • 하지만 이렇게 해서 끝이 나면 안된다. 처음에 답이 왜 안나오나 했는데 DFS탐색에서는 凸 모양이 안되기 때문이다

    👉 따라서 이 모양만 따로 처리해주었다.

    public static int ExceptionShape(int x, int y) {
  int size = 1;//현재 자기 자신
  int sum = map[y][x];//현재 자기 자신
  int minValue = Integer.MAX_VALUE; //상하좌우중 가장 작은 것 고르기 위해서
  for (int i = 0; i < 4; i++) {
    int nextX = x + dx[i];
    int nextY = y + dy[i];
      
    if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N ) continue;
    size++;//상하좌우 볼때마다 사이즈를 1증가시킨다
    sum += map[nextY][nextX];//상하좌우 볼때마다 값을 더한다
    minValue = Math.min(minValue, map[nextY][nextX]);//상하좌우중 가장 작은 값을 뽑는다
  }
  
  if (size == 4) return sum;//4개라면 딱 凸 모양이므로 그 값을 return한다
  else if (size == 5) return sum - minValue;//5개라면 거기서 제일 작은 것을 빼면 가장 큰 4개가 된다.
  else return 0;
}

    이 경우 현재 위치에서 상하좌우를 보고, 상하좌우중 가장 작은 값을 빼면 그것이 현재 위치에서 가장 큰 凸(회전될수도 있고 ~ ) 이 될것이다.

느낀점

갑자기 백트래킹을안해서 왜 안나오지? 이러다 디버깅 해서야 왜 답이 안나온줄 알았다..왜그랬지 하~

  • 문제: https://www.acmicpc.net/problem/14500
  • 저장소: https://github.com/yoo-chaewon/HELLO_JAVA/blob/master/Algorithm/1.BOJ/SAMSUNG_SW/Q_14500_테트로미노.java

참고