Algorithm/Problem Solving

[백준/BOJ]14500번 테트로미노

NAWIN 2020. 1. 11. 03:00
반응형

구현이 너무 귀찮았던 문제였다.

도형이 나올 수 있는 가지수가 19가지 였는데 이걸 하나하나 구현하는게 너무 힘들었다ㅜㅜ

 

같이 푼 스터디의 선배가 노가다 말고 엄청나게 똑똑한 방법을 설명해 줬는데, 설명듣고 너무 똑똑해서 여러번 감탄한 문제였다.

정말... 하나의 아이디어가 엄청난 효율을 낼 수 있다는 걸 알게해 준 문제.. 지금 올리는건 내가 푼 코드만 올리는거지만 조만간 알게된 방법으로도 풀어봐야겠다.

 

 

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누

www.acmicpc.net

방법 1) 모든 도형 구현해서 값구하고 배열 한바퀴돌아서 최대값구하기

방법 2) dfs를 이용한 방법인데 저 도형이 크기가4인 dfs를 돌렸을때 나오는 모든 가지수와 같다.(ㅗ,ㅏ,ㅜ,ㅓ 모양 제외)

          배열 한바퀴 돌면서 각 자리에서 dfs를 돌려 그중 최대값 구하기

 

 

 

<코드>

범위를 고려해서 짜니까 예제(질문검색예제포함) 모두 답이 나오는데 답이 자꾸 틀려서 범위 생각하지않으려고

처음시작 인덱스를 (3,3)으로 했다. 해당 범위 외에는 모두 0으로 채워서 최대값에는 영향을 미치지 않는다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
using namespace std;
int adj[510][510] = { 0 };
int N,M;
int te(int x, int y) {
	int sum[19];
	sum[0] = adj[x][y] + adj[x + 1][y] + adj[x + 2][y] + adj[x + 3][y];
	sum[1] = adj[x][y] + adj[x][y + 1] + adj[x][y + 2] + adj[x][y + 3];

	sum[2] = adj[x][y] + adj[x + 1][y] + adj[x][y + 1] + adj[x + 1][y + 1];

	sum[3] = adj[x][y] + adj[x + 1][y] + adj[x + 2][y] + adj[x + 2][y + 1];
	sum[4] = adj[x][y] + adj[x][y + 1] + adj[x][y + 2] + adj[x - 1][y + 2];
	sum[5] = adj[x][y] + adj[x][y + 1] + adj[x][y + 2] + adj[x + 1][y];
	sum[6] = adj[x][y] + adj[x][y + 1] + adj[x + 1][y + 1] + adj[x + 2][y + 1];

	sum[7] = adj[x][y] + adj[x + 1][y] + adj[x +1][y +1] + adj[x+1 ][y + 2];
	sum[8] = adj[x][y] + adj[x + 1][y] + adj[x + 2][y] + adj[x][y + 1];
	sum[9] = adj[x][y] + adj[x][y + 1] + adj[x][y + 2] + adj[x + 1][y + 2];
	sum[10] = adj[x][y] + adj[x][y + 1] + adj[x - 1][y + 1] + adj[x - 2][y + 1];

	sum[11] = adj[x][y] + adj[x][y + 1] + adj[x + 1][y + 1] + adj[x + 1][y + 2];
	sum[12] = adj[x][y] + adj[x - 1][y] + adj[x - 1][y + 1] + adj[x - 2][y + 1];
	sum[13] = adj[x][y] + adj[x][y + 1] + adj[x - 1][y + 1] + adj[x - 1][y + 2];
	sum[14] = adj[x][y] + adj[x + 1][y] + adj[x + 1][y + 1] + adj[x + 2][y + 1];
	
	sum[15] = adj[x][y] + adj[x][y + 1] + adj[x][y + 2] + adj[x - 1][y + 1];
	sum[16] = adj[x][y] + adj[x + 1][y] + adj[x + 2][y] + adj[x + 1][y + 1];
	sum[17] = adj[x][y] + adj[x][y + 1] + adj[x][y + 2] + adj[x + 1][y + 1];
	sum[18] = adj[x][y] + adj[x + 1][y] + adj[x + 2][y] + adj[x+1][y - 1];
	
	int m = 0;
	for (int i = 0; i < 19; i++) {
		if (m < sum[i])m = sum[i];
	}
	return m;
}
int main(void) {
	//int N, M;
	scanf("%d %d", &N, &M);
	for (int i = 3; i < N+3; i++) {
		for (int j = 03; j < M+3; j++) {
			cin >> adj[i][j];
		}
	}
	int re =0;
	for (int i = 3; i < N+3; i++) {
		for (int j = 3; j < M+3; j++) {
			int pre=te(i, j);
			if (pre >re)re = pre;
		}
	}
	printf("%d\n", re);
	return 0;
}
반응형