백준 14500번 테트로미노 (삼성 SW 역량테스트 기출문제)

사용한 알고리즘: 브루스 포스, 구현...?


삼성 기출은 굉장히 구현문제가 많은 것 같습니다.
우리 화이팅 해 봅시다...!

우선 문제에서 주어진 폴리오미노(?)를 대칭, 회전 모두 가능하다 했기에
주어진 세가지 조건
1. 정사각형은 겹치지 않는다.
2. 도형은 모두 연결되어 있어야 한다.
3. 정사각형 끼리는 변으로 연결되어야 한다.
를 기준으로 생각했습니다.

먼저 (0,0) 사각형부터 끝 지점 까지 모든 사각형을 훑었습니다. (브루스 포스 - 완전탐색)
단 i 번째 사각형을 볼 때 좌,우,아래 사각형만 보고 사각형은 보지 않는 식으로 중첩을 최소화 하려고 했습니다.
함수를 하나 만들고 추가 블록 개수를 저장 (처음엔 4개) 하며 재귀형식으로 함수를 돌렸습니다.
(1) i 번째 사각형에서 추가 블록 개수가 (자신 제외)  i번째 사각형이 맞닿아 있는 (아직 쓰지않은) 사각형 개수보다 작은 경우
(2) 추가 블록 개수가 1 보다 큰경우 ( 추가 블록 개수가 1 인 경우는 (1)과정에서 이미 생각)
     아래 사각형으로 이동, 왼쪽 사각형으로 이동, 오른쪽 사각형으로 이동

위와같이 크게 2개의 과정으로 생각하여,
함수를 돌릴 때 과정(1) 의 경우는 그냥 노가다 해서 구했고,
(2) 의 경우는 재귀형태로 구해서
각 과정마다 구하고자 하는 최대값을 최신화 해 주었습니다.

푸는 방식 자체는 어렵지 않고, 다양한 풀이가 있을 거라고 생각됩니다.
(물론 저보다 훨씬 깔끔하게 푸는 분들도 많을 겁니다..!!)
포인트는 누가 실수를 안하고 구현을 하느냐 였던 문제인 것 같습니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 재귀, 브루트 포스
	int N, M, ans, arr[501][501];
	bool visited[501][501];
	// 위로 올라가진 않을것입니다.
	void MaxAns(int x, int y, int cnt, int temp){
	temp+=arr[x][y];
	cnt--;
	// 인접 사각형 보는 경우
	int near = 0;
	if(x+1<N && !visited[x+1][y]) near++;
	if(y-1>=0 && !visited[x][y-1]) near++;
	if(y+1<M && !visited[x][y+1]) near++;
	if(near>=cnt){
	int ttt = 0;
	if(cnt==3){
	ttt+=(arr[x+1][y]+arr[x][y-1]+arr[x][y+1]);
	ans=max(ans, temp+ttt);
	}
	else if(cnt==2){
	if(near==2){
	if(x+1<N && !visited[x+1][y]) ttt+=arr[x+1][y];
	if(y-1>=0 && !visited[x][y-1]) ttt+=arr[x][y-1];
	if(y+1<M && !visited[x][y+1]) ttt+=arr[x][y+1];
	ans=max(ans,temp+ttt);
	}
	else if(near==3){
	ttt+=(arr[x+1][y]+arr[x][y-1]);
	ans=max(ans,temp+ttt);
	ttt=0;
	ttt+=(arr[x+1][y]+arr[x][y+1]);
	ans=max(ans,temp+ttt);
	ttt=0;
	ttt+=(arr[x][y-1]+arr[x][y+1]);
	ans=max(ans,temp+ttt);
	ttt=0;
	}
	}
	else if(cnt==1){
	if(x+1<N && !visited[x+1][y]) ttt+=arr[x+1][y];
	ans=max(ans,temp+ttt);
	ttt=0;
	if(y-1>=0 && !visited[x][y-1]) ttt+=arr[x][y-1];
	ans=max(ans,temp+ttt);
	ttt=0;
	if(y+1<M && !visited[x][y+1]) ttt+=arr[x][y+1];
	ans=max(ans,temp+ttt);
	}
	}
	if(cnt==1) return;
	// DFS 돌아야 되는 경우 (cnt>1 인 경우)
	visited[x][y] = true;
	if(x+1<N && !visited[x+1][y]) MaxAns(x+1,y,cnt,temp);
	if(y-1>=0 && !visited[x][y-1]) MaxAns(x,y-1,cnt,temp);
	if(y+1<M && !visited[x][y+1]) MaxAns(x,y+1,cnt,temp);
	visited[x][y] = false;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < M; ++j)
	cin >> arr[i][j];
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < M; ++j){
	MaxAns(i,j,4,0);
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 14500.cpp hosted with ❤ by GitHub