[C++] 백준 14500 테트로미노

문제 링크

---

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

14500번: 테트로미노

접근 방법

---

 시작지점부터 상하좌우로 인접한 지점을 따라가며 백트래킹을 하여 테트로미노를 이루는 4칸이 완성이 되었을 때 최댓값을 갱신해주며 풀면 된다. 하지만 주의해야될 점이있다. 

 

 

 이런 경우에 3과 4는 인접해 있지 않지만 위와 같은 경우도 문제에서 요구하는 경우의 수가 되기 때문이다.

이 점을 유의하여 문제를 풀어보자.

if (cnt == 3) {
	if (stk[0].x == stk[1].x && stk[1].x == stk[2].x) {
		info fuck[2] = { {1, 0} ,{-1, 0} };
		for (int i = 0; i < 2; i++) {
			int next_x = stk[1].x + fuck[i].x;
			int next_y = stk[1].y + fuck[i].y;
			if (0 <= next_x && next_x < N && 0 <= next_y && next_y < M && !visited[next_x][next_y]) {
				visited[next_x][next_y] = true;
				stk.push_back({ next_x, next_y });
				solve(cnt + 1, next_x, next_y);
				stk.pop_back();
				visited[next_x][next_y] = false;
			}
		}
	}
}

 일단 그림에서 설명한 것과 동일하게 3개의 폴리오미노가 수평으로 나란할 때, 즉 코드상으로 x의 값이 동일 할때에 대한 처리 부분이다. 수직으로 나란한 경우도 크게 다른점이 없으니 수평인 경우만 설명하겠다.

 

 일단 3개의 폴리오미노가 이루어졌을 때 -> if(cnt == 3) ) 지금까지 이룬 폴리오미노의

집합 stk[i] (0 <= i < 3) 의 x값이 모두 동일 하다면 -> if (stk[0].x == stk[1].x && stk[1].x == stk[2].x)

3개의 폴리오미노중 가운대인 stk[1]에 위 아래 방향으로 더하여(int next_x = stk[1].x + fuck[i].x,  
int next_y = stk[1].y + fuck[i].y) 다음 스탭으로 진행을 시키면 된다. 

  

소스 코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct info {
	int x;
	int y;
};

vector <info> stk;
info next_dir[4] = { {1,0}, {-1,0}, {0,-1}, {0,1} };
int map[500][500];
bool visited[500][500];
int N, M;
int result = -1;

void solve(int cnt, int x, int y) {
	if (cnt == 4) {
		int sum = 0;
		for (int i = 0; i < 4; i++) {
			sum += map[stk[i].x][stk[i].y];
			result = max(result, sum);
		}
		return;
	}
	if (cnt == 3) {
		if (stk[0].x == stk[1].x && stk[1].x == stk[2].x) {
			info fuck[2] = { {1, 0} ,{-1, 0} };
			for (int i = 0; i < 2; i++) {
				int next_x = stk[1].x + fuck[i].x;
				int next_y = stk[1].y + fuck[i].y;
				if (0 <= next_x && next_x < N && 0 <= next_y && next_y < M && !visited[next_x][next_y]) {
					visited[next_x][next_y] = true;
					stk.push_back({ next_x, next_y });
					solve(cnt + 1, next_x, next_y);
					stk.pop_back();
					visited[next_x][next_y] = false;
				}
			}
		}
		else if (stk[0].y == stk[1].y && stk[1].y == stk[2].y){
			info fuck[2] = { {0, 1} ,{0, -1} };
			for (int i = 0; i < 2; i++) {
				int next_x = stk[1].x + fuck[i].x;
				int next_y = stk[1].y + fuck[i].y;
				if (0 <= next_x && next_x < N && 0 <= next_y && next_y < M && !visited[next_x][next_y]) {
					visited[next_x][next_y] = true;
					stk.push_back({ next_x, next_y });
					solve(cnt + 1, next_x, next_y);
					stk.pop_back();
					visited[next_x][next_y] = false;
				}
			}
		}
	}
	for (int i = 0; i < 4; i++) {
		int next_x = x + next_dir[i].x;
		int next_y = y + next_dir[i].y;
		if (0 <= next_x && next_x < N && 0 <= next_y && next_y < M && !visited[next_x][next_y]) {
			visited[next_x][next_y] = true;
			stk.push_back({ next_x, next_y });
			solve(cnt + 1, next_x, next_y);
			stk.pop_back();
			visited[next_x][next_y] = false;
		}
	}

}

int main() {

	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = true;
			stk.push_back({ i,j });
			solve(1, i, j);
			stk.pop_back();
			visited[i][j] = false;
		}
	}
	cout << result << "\n";
}

개발 환경 : VS 2019

질문, 지적 환영입니다.