[골드4] 14500. 테트로미노 (Java)

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

14500번: 테트로미노

Thanks to 릴라좌

---

※  문제를 요약하면 아래와 같습니다.

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

▶ 크기가 NxM인 각각의 칸에 값을 가지고 있는 종이 위에 테트로미노 하나를 놓으려고함

▶ 이 때 테트로미노 중 하나를 종이 위에 놓을 수 있는 경우 중에 테트로미노 칸안의 수의 합들 가장 큰 값을 출력

▶ 각 테트로미노는 회전, 대칭하여 종이위에 놓는 것이 가능

▶ Input : 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 공백을 구분으로 입력

                이후 N개의 줄에 맵의 값 입력

▶ Output : 테트로미노가 놓일 수 있는 경우의 수 중 칸안의 수의 합이 최대값인 것을 출력

---

◈ Input - 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

◈ Output - 1

19

◈ Input - 2

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

◈ Output - 2

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

◈ Input - 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

◈ Output - 3

7

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 'ㅜ' 모양을 제외한 나머지 테트로미노 의 대칭, 회전 경우의 수를 아래와 같이 확인

    1. 빨간점을 시작점으로 탐색을 진행을 가정,

    2. 'ㅜ'모양을 제외한 나머지 모양의 대칭 및 회전하여 놓는 모든 경우의 수를 아래와 같이 표현

     3. 겹치면 아래와 같이 되며,

   

     4. 시작점을 중심으로 상,하,좌,우로 4칸 탐색 시 가능한 모든 경우의 수의 표현과 동일한 것을 확인 

▶ 위의 규칙으로 DFS를 델타 탐색으로 상하좌우를 탐색, 4칸 탐색 시 해당 칸들의 합과 최대값을 비교

▶ 'ㅜ'모양의 경우 위의 규칙에 해당 되지 않으므로 회전과 대칭이 가능한 범위를 직접 탐색

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int N, M, nMax;
	static int[][] narrMap;
	static boolean[][] barrVisit;

	// 동, 서, 남, 북
	static int[] dr = { 0, 0, 1, -1 };
	static int[] dc = { 1, -1, 0, 0 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		// map 값 입력 받자
		narrMap = new int[N][M];
		barrVisit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bReader.readLine());
			for (int j = 0; j < M; j++) {
				narrMap[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		nMax = 0;
		// 첫번째 칸 부터 완전 탐색 돌리자
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				//barrVisit = new boolean[N][M];
				// ㅜ 모양을 제외한 나머지는 DFS로 4칸만 탐색하면 된다 (feat.릴라좌 땅큐)
				barrVisit[i][j] = true;
				DFS(i, j, narrMap[i][j], 0);
				barrVisit[i][j] = false;
				// ㅜ 모양을 대칭 or 회전했을 때 max값과 비교하자
				for(int k = 1; k <= 4; k++)
					FuShape(i, j, k);
			}
		}
		
		bWriter.write(String.valueOf(nMax));
		bWriter.close();
	}

	// 4칸 탐색 고고하자
	private static void DFS(int nRow, int nCol, int nSum, int nDepth) {
		// 기저 조건
		// ㅗ모양을 제외한 나머지는 4번 탐색을 진행
		if (nDepth == 3) {
			nMax = Math.max(nMax, nSum);
			return;
		}

		// 재귀 조건
		for (int i = 0; i < 4; i++) {
			int nSearchRow = nRow + dr[i];
			int nSearchCol = nCol + dc[i];

			// 방문했거나 범위 밖이면 패쓰
			if (nSearchRow < 0 || nSearchCol < 0 || nSearchRow >= N || nSearchCol >= M
					|| barrVisit[nSearchRow][nSearchCol])
				continue;

			
			// Depth가 4인 모든 곳을 탐색하기 위해
			// 해당 칸에 이어진 Depth 탐색 시 방문처리에 true값 넣어주고
			// 해당 칸에 이어진 탐색 종료 시 false로 변경
			barrVisit[nSearchRow][nSearchCol] = true;
			DFS(nSearchRow, nSearchCol, nSum + narrMap[nSearchRow][nSearchCol], nDepth + 1);
			barrVisit[nSearchRow][nSearchCol] = false;
		}
	}

	// ㅗ모양 탐색하자
	private static void FuShape(int nRow, int nCol, int nNum) {
		// 현재 점을 중심으로 ㅗ모양을 대칭 및 방향전환 했을 때 가능한 탐색 구간 고고
		int nSum = narrMap[nRow][nCol];
		// ㅗ 모양
		if (nNum == 1) {
			// 배열의 범위 체크는 필수~
			if (nRow + 1 >= N || nCol - 1 < 0 || nCol + 1 >= M)
				return;
			nSum += narrMap[nRow][nCol - 1];
			nSum += narrMap[nRow + 1][nCol];
			nSum += narrMap[nRow][nCol + 1];
		}
		// ㅏ 모양
		if (nNum == 2) {
			// 배열의 범위 체크는 필수~
			if (nRow + 1 >= N || nRow - 1 < 0 || nCol + 1 >= M)
				return;
			nSum += narrMap[nRow + 1][nCol];
			nSum += narrMap[nRow][nCol + 1];
			nSum += narrMap[nRow - 1][nCol];
		}
		// ㅜ 모양
		if (nNum == 3) {
			// 배열의 범위 체크는 필수~
			if (nRow - 1 < 0 || nCol - 1 < 0 || nCol + 1 >= M)
				return;
			nSum += narrMap[nRow][nCol - 1];
			nSum += narrMap[nRow - 1][nCol];
			nSum += narrMap[nRow][nCol + 1];
		}
		// ㅓ 모양
		if (nNum == 4) {
			// 배열의 범위 체크는 필수~
			if (nRow + 1 >= N || nRow - 1 < 0 || nCol - 1 < 0)
				return;
			nSum += narrMap[nRow + 1][nCol];
			nSum += narrMap[nRow][nCol - 1];
			nSum += narrMap[nRow - 1][nCol];
		}
		// max와 비교해보자
		nMax = Math.max(nSum, nMax);
	}
}

Have a great day~ :)