[Algorithm] 백준 14500(BOJ 14500) 테트로미노 문제풀이!! (Java)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 14500번 테트로미노 문제를 풀어보겠습니다.

문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다.

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

 

1. 문제 설명

해당 문제를 풀고 나서 다른 분들의 풀이를 보니 BFS나 DFS를 활용해서 푸시는 분들도 있었고 테트로미노의 모양 전부를 체크해서 문제를 푸는 분들도 있었습니다.

저는 탐색 알고리즘보다는 19개 모양에 대해서 모두 탐색해서 값을 구하는 방법으로 구현했습니다.

테트로미노 모양을 보면 긴 막대와 정사각형 모양을 제외하고는 모두 공통된 형태에 포함됩니다.

예를 들어 2개의 행과 3개의 열로 이루어진 직사각형에서 첫 행의 1,2번 열의 칸을 제외하면 "┙"모양의 테트로미노를 구할 수 있습니다.

이런 방법을 통해 6개의 칸의 값을 길이가 6인 배열에 모두 저장하고 2개의 칸만 제외해나가면, 해당 직사각형에 포함되는 테트로미노들을 구할 수 있습니다.

그럼 코드로 살펴보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingknowjam.algorithm.boj;

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

public class BOJ_14500 {
	private static int result = 0;
	private static int otherResult = 0;
	private static int R = 0;
	private static int C = 0;
	private static int[][] map;
	private static int[] arr = new int[6];

	public static void main(String[] args) throws IOException {
		// 입력을 빋는 객체
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 행과 열 정보 입력받고 2차원 배열 생성
		String[] NM = br.readLine().split(" ");
		R = Integer.parseInt(NM[0]);
		C = Integer.parseInt(NM[1]);
		map = new int[R][C];

		// 2차원 배열 맵 초기화
		initMap(br);

		// 행1 열4 형태로 구성된 테트로미노 값 연산
		R1C4();
		// 행4 열1 형태로 구성된 테트로미노 값 연산
		R4C1();
		// 행2 열2 형태로 구성된 테트로미노 값 연산
		R2C2();
		// 행2 열3 형태로 구성된 테트로미노 값 연산
		R2C3();
		// 행3 열2 형태로 구성된 테트로미노 값 연산
		R3C2();

		// 결과값 출력
		System.out.println(result);
	}

	/**
	 * 2차원 배열 초기화
	 */
	private static void initMap(BufferedReader br) throws IOException {
		for (int i = 0; i < R; i++) {
			String[] tempString = br.readLine().split(" ");
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(tempString[j]);
			}
		}
	}

	/**
	 * 결과 값 갱신 메서드
	 * otherResult와 result중 큰 값으로 갱신
	 */
	private static void updateResult(int otherResult) {
		result = Math.max(result, otherResult);
	}

	/**
	 * 파라미터 인덱스를 제외한 배열의 합 구하기
	 * 6개의 칸을 가진 테트로미노들에서 사용
	 */
	private static int getSumTetromino(int firstIndex, int secondIndex, int[] arr) {
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			if (firstIndex == i || secondIndex == i) {
				continue;
			}
			sum += arr[i];
		}
		return sum;
	}

	/**
	 * □□□□ 구하기
	 */
	private static void R1C4() {
		for (int i = 0; i < R; i++) {
			int lt = 0;
			otherResult = map[i][0] + map[i][1] + map[i][2] + map[i][3];
			updateResult(otherResult);
			for (int rt = 4; rt < C; rt++) {
				otherResult = otherResult + map[i][rt] - map[i][lt];
				updateResult(otherResult);
				lt++;
			}
		}
	}

	/**
	 * □ 구하기
	 * □
	 * □
	 * □
	 */
	private static void R4C1() {
		for (int i = 0; i < C; i++) {
			int lt = 0;
			otherResult = map[0][i] + map[1][i] + map[2][i] + map[3][i];
			updateResult(otherResult);
			for (int rt = 4; rt < R; rt++) {
				otherResult = otherResult + map[rt][i] - map[lt][i];
				updateResult(otherResult);
				lt++;
			}
		}
	}

	/**
	 * □□ 구하기
	 * □□
	 */
	private static void R2C2() {
		for (int i = 0; i < R - 1; i++) {
			int lt = 0;
			otherResult = map[i][0] + map[i][1] + map[i + 1][0] + map[i + 1][1];
			updateResult(otherResult);
			for (int rt = 2; rt < C; rt++) {
				otherResult = otherResult + map[i][rt] + map[i + 1][rt]
					- map[i][lt] - map[i + 1][lt];
				updateResult(otherResult);
				lt++;
			}
		}
	}

	/**
	 * □□□ 에 포함되는 테트로미노들 구하기
	 * □□□
	 */
	private static void R2C3() {
		for (int i = 0; i < R - 1; i++) {
			for (int j = 0; j < C - 2; j++) {
				arr[0] = map[i][j];
				arr[1] = map[i][j + 1];
				arr[2] = map[i][j + 2];
				arr[3] = map[i + 1][j];
				arr[4] = map[i + 1][j + 1];
				arr[5] = map[i + 1][j + 2];

				otherResult = getSumTetromino(0, 2, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(3, 5, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(2, 3, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(0, 5, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(0, 1, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(1, 2, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(4, 5, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(3, 4, arr);
				updateResult(otherResult);
			}
		}
	}

	/**
	 * □□ 에 포함되는 테트로미노들 구하기
	 * □□
	 * □□
	 */
	private static void R3C2() {
		for (int i = 0; i < R - 2; i++) {
			for (int j = 0; j < C - 1; j++) {
				arr[0] = map[i][j];
				arr[1] = map[i][j+1];
				arr[2] = map[i+1][j];
				arr[3] = map[i+1][j+1];
				arr[4] = map[i+2][j];
				arr[5] = map[i+2][j+1];

				otherResult = getSumTetromino(0, 4, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(1, 5, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(1, 4, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(0, 5, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(0, 2, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(1, 3, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(2, 4, arr);
				updateResult(otherResult);

				otherResult = getSumTetromino(3, 5, arr);
				updateResult(otherResult);
			}
		}
	}
}

 

코드마다 주석을 달아보려고 했는데, 말로 설명하기 조금 어려운 부분들이 있어서 전부 작성하지는 않았습니다.

앞서 설명드린 구현 방법과 같이 예시 데이터 하나를 넣어서 쭉 따라가 보시면 어렵지 않게 이해할 수 있을 거라 생각합니다.

감사합니다.

---