백준 14500 테트로미노

테트로미노 링크: https://www.acmicpc.net/problem/14500

14500번: 테트로미노

프로젝트가 저번주에 끝나서 오랜만에 알고리즘 풀시간이 생겼네요

오랜만에 푸는거라 감 잃었을까봐 가볍게 골드5 풀어봤습니다.

문제는 테트로미노에요 .

다음의 테트로미노 도형을 회전, 대칭해서 숫자가 적혀있는 map에 하나를 올려놓았을때 가장 큰수를 출력하는 문제 였습니다.

 

저번과 같이 브루트포스 문제였는데요.

저는 도형이 5개밖에 되지 않기 때문에 나올 수 있는 모든 도형을 정의 했습니다.

5개의 도형을 회전하거나 대칭하게되면 다음과 같은 도형들이 생기게 됩니다

발그림 죄송합니다;;ㅋㅅㅋ

쨋든 총 19개의 도형들이 생기고 이를 코드상에서

 

이런식으로 정의를 했어요. 꽤나 노가다였지만 제일 확실하고 이후에 편할꺼 같아서;;;ㅋ

이후에는 저중에서 순차적으로 도형 하나를 선택해서 맵의 좌측 상단부터 우측하단까지 모든 값을 구했습니다.

 

아래는 코드에용~~

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

public class 테트로미노 {

	static int N, M;// 세로 가로
	static int[][] map;
	static int answer = 0;
	static int[][][] allTet = { { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 } }, { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 } },
			{ { 0, 0 }, { 0, 1 }, { 1, 0 }, { 1, 1 } }, { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 2, 1 } },
			{ { 0, 0 }, { 1, 0 }, { 0, 1 }, { 0, 2 } }, { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 2, 1 } },
			{ { 1, 0 }, { 1, 1 }, { 1, 2 }, { 0, 2 } }, { { 0, 1 }, { 1, 1 }, { 2, 1 }, { 2, 0 } },
			{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 2 } }, { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 0, 1 } },
			{ { 0, 0 }, { 1, 0 }, { 1, 1 }, { 1, 2 } }, { { 0, 0 }, { 1, 0 }, { 1, 1 }, { 2, 1 } },
			{ { 1, 0 }, { 1, 1 }, { 0, 1 }, { 0, 2 } }, { { 0, 1 }, { 1, 1 }, { 1, 0 }, { 2, 0 } },
			{ { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 2 } }, { { 1, 0 }, { 1, 1 }, { 1, 2 }, { 0, 1 } },
			{ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 1, 1 } }, { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 1 } },
			{ { 1, 0 }, { 0, 1 }, { 1, 1 }, { 2, 1 } } };

	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());
		map = new int[N][M];

		for (int n = 0; n < N; n++) {

			st = new StringTokenizer(br.readLine());

			for (int m = 0; m < M; m++) {
				map[n][m] = Integer.parseInt(st.nextToken());
			}
		}

		for (int t = 0; t < 19; t++) {
			// 테트로미노 도형을 하나 뽑아 오는 작업
			int[][] tetShape = allTet[t].clone();
			int sum = map[tetShape[0][0]][tetShape[0][1]] + map[tetShape[1][0]][tetShape[1][1]]
					+ map[tetShape[2][0]][tetShape[2][1]] + map[tetShape[3][0]][tetShape[3][1]];

			int[][] tempTetShape = new int[4][2];

			for (int y = 0; y < N; y++) {

				for (int i = 0; i < tempTetShape.length; i++) {
					System.arraycopy(tetShape[i], 0, tempTetShape[i], 0, tetShape[i].length);
				}

				for (int z = 0; z < 4; z++) {
					tempTetShape[z][0] += y;
				}

				if (outOfBoundary(tempTetShape)) {
					break;
				}

				for (int x = 0; x < M; x++) {
					if (x != 0) {
						for (int z = 0; z < 4; z++) {
							tempTetShape[z][1] += 1;
						}
					}

					if (outOfBoundary(tempTetShape)) {
						break;
					}

					int newSum = map[tempTetShape[0][0]][tempTetShape[0][1]]
							+ map[tempTetShape[1][0]][tempTetShape[1][1]] + map[tempTetShape[2][0]][tempTetShape[2][1]]
							+ map[tempTetShape[3][0]][tempTetShape[3][1]];

					sum = sum < newSum ? newSum : sum;
				}
			}
			answer = answer < sum ? sum : answer;
		}

		System.out.println(answer);
	}

	public static boolean outOfBoundary(int[][] arr) {
		int size = arr.length;
		for (int s = 0; s < size; s++) {
			if (arr[s][0] < 0 || arr[s][1] < 0 || arr[s][0] >= N || arr[s][1] >= M) {
				return true;
			}
		}
		return false;
	}
}

 

다풀고나서 제출하니 87%에서 틀리길래 봤더니 x쪽으로 옮길때 x가 1부터 시작하게하고 if(x!=0)이 구문이 없어서 바로 +1한값을 계산하더라구요;;; 이거 잡는대 30분걸림;;; 저같이 바보같은 실수 하지 않으시길 바라겠습니다.ㅎ