[백준] 14500: 테트로미노 (DFS, dydx) - JAVA

class3++ 

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

 

 

 

# 문제

 

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

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

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

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×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

 

출력

19

 

# 필요개념

진짜 테트리스 게임처럼 회전만 가능한줄 알았는데, 대칭도 가능하다 해서 완전탐색으로 풀어야겠다 ! 하고 생각하고 있었다. 그렇게 풀고 나니 한 가지가 걸렸다.

 

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

 

이렇게 입력이 주어졌을 때, 내 코드로는 6이 나오지만, 답은 7이라는 것이다. 나머지 테트로미노와 달리 분홍색 테트로미노는 두번째 타일에서 한번 더 탐색할 수 있어야 한다!! 이 점을 잊고 마냥 상하좌우 탐색으로 풀었던 것이다 ,,,,,,,

 

그래서 dfs로 풀되, 두번째 탐색에서는 한번 더 탐색할 수 있도록 코드를 추가해주었다.

 

추가로, 인덱스 범위도 잘 살펴주어야 한다. 나는 이 부분은 range() 메소드를 생성해 잡아주었다.

 

# Code

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static int[] dy = {-1, 0, 1, 0}; // 위 오 아 왼
    static int[] dx = {0, 1, 0, -1};
    static int ans = 0;
    static int[][] inputs;
    static boolean[][] isVisit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        inputs = new int[N][M];
        isVisit = new boolean[N][M];

		// 입력받기
        for (int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0 ; j < M ; j++) {
                inputs[i][j] = Integer.parseInt(st.nextToken());
            }
        }

		// 완전탐색
        for (int i = 0 ; i < N ; i++) {
            for (int j = 0 ; j < M ; j++) {
                isVisit[i][j] = true;
                dfs(i, j, 1, inputs[i][j]);
                isVisit[i][j] = false;
            }
        }
        System.out.println(ans);
    }
    private static void dfs(int y, int x, int cnt, int sum) {
        if (cnt == 4) {
            ans = Math.max(ans, sum);
            return ;
        }
        for (int i = 0 ; i < 4 ; i++) {
            int row = y + dy[i];
            int col = x + dx[i];
            if (range(row, col) &&  !isVisit[row][col]) {
                if (cnt == 2) { // 두번째 타일에서 한번 더 탐색
                    isVisit[row][col] = true;
                    dfs(y, x, cnt + 1, sum + inputs[row][col]);
                    isVisit[row][col] = false;
                }
                isVisit[row][col] = true;
                dfs(row, col, cnt + 1, sum + inputs[row][col]);
                isVisit[row][col] = false;
            }
        }
    }

    private static boolean range(int y, int x) {
        return y >= 0 && y < N && x >= 0 && x < M;
    }
}

 

# 결과