백준 14500 c++ "테트로미노" -PlusUltraCode-

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

 

[필자 코드]

하나의 불록에서 시작하여 점차 블록을 하나하나 덧붙여 총 4개의 정사각형 블록을 이어 붙인다음
최대값을 찾는 문제이다.

 

필자는 이러한 과정을 DFS를 이용하여 구현했다.

 

다만 문제가 생겼다.

 

문제에서 보여진 5개의 도형중 학교모형은 DFS로 구현이 불가능 하다는 점이다.

혹시 다른 알고리즘이 있나 생각해 봤지만 내가 배운 범위내에선 없는 것으로 보아

직접구현을 통해 specialCase를 구하고 다른 분들의 풀이도 본 결과

내 판단이 맞았다.

아래는 소스코드 해설이다.

1. 입력 받기

• 먼저 2차원 배열의 크기와 배열에 들어갈 값들을 입력 받습니다. 이 배열은 N x M 크기입니다. 또한, 노드를 방문했는지 여부를 기록하기 위한 visited 배열도 동일한 크기로 설정합니다.

2. 경계 체크

• 배열의 각 좌표에 대해 유효한 범위 내에 있는지 확인하는 함수를 통해, 배열 바깥으로 나가는 잘못된 좌표로 이동하지 않도록 제한합니다.

3. 깊이 우선 탐색(DFS)

• DFS는 재귀적으로 2차원 배열의 각 좌표에서 출발하여, 상하좌우 네 방향으로 이동하면서 경로를 탐색합니다.
• 경로의 길이가 4에 도달할 때까지 탐색하며, 경로에서 방문한 노드들의 값을 합산합니다. 길이가 4에 도달하면 해당 경로의 합을 현재까지 계산한 최대값과 비교하여, 더 큰 값을 저장합니다.
• 한 번 방문한 노드는 다시 방문하지 않도록 기록하지만, 다른 경로를 탐색할 때 다시 방문할 수 있도록 탐색이 끝난 후에는 방문 기록을 해제합니다. 이는 백트래킹 기법입니다.
• 이렇게 함으로써 모든 가능한 경로를 탐색하면서 최댓값을 찾습니다.

4. 특별한 경우 처리

• DFS 탐색만으로는 찾을 수 없는 특정 모양의 경로(예: 'ㅗ', 'ㅏ', 'ㅓ', 'ㅜ' 모양)를 처리하는 추가적인 단계가 필요합니다. 이 모양은 중앙 노드를 기준으로 상하좌우 중 3개의 방향에 있는 노드들을 포함하는 구조로, DFS로는 이 모양을 만들 수 없습니다.
• 이를 처리하기 위해 각 좌표에서 상하좌우 4개의 값을 확인하여, 그중 3개의 값과 현재 노드의 값을 더해 해당 경로의 합을 계산합니다. 이 값도 마찬가지로 최댓값을 갱신하는 방식으로 처리됩니다.
• 만약 상하좌우 중 2개 이상의 방향이 배열 경계를 벗어나면 이 모양을 만들 수 없으므로 계산을 건너뜁니다.

5. 모든 좌표에 대해 탐색

• 배열의 모든 좌표를 시작점으로 하여 DFS 탐색과 특별한 경우 처리를 각각 수행합니다.
• 각 좌표에서 출발한 경로들 중에서 가장 큰 값을 찾아내고, 그 값을 출력합니다.

6. 최종 결과 출력

• 최종적으로, 배열 내에서 가능한 모든 경로 중에서 값을 더했을 때 가장 큰 합을 출력합니다.

핵심 개념

• DFS 탐색: 상하좌우로 노드를 이동하면서 경로를 찾아가는 탐색 방법입니다. 각 경로는 길이가 4가 될 때까지만 탐색합니다.
• 백트래킹: 이미 방문한 노드는 다시 방문하지 않도록 하면서, 탐색이 끝난 후에는 방문 기록을 초기화하여 다른 경로를 탐색할 수 있도록 하는 기법입니다.
• 특별한 경우 처리: DFS로는 처리할 수 없는 특정 모양(‘ㅗ’ 모양 등)을 따로 계산하여, 이 모양의 경로에서 얻을 수 있는 최대 합도 고려합니다.
• 최댓값 갱신: 각 경로의 합을 계산할 때마다 현재까지 계산된 최대값과 비교하여 더 큰 값을 저장합니다.

 

 

[소스 코드]

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

using namespace std;


int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

typedef pair<int, int> Node;

int N, M;
int resultMax = -1;
vector<vector<int>> arr;
vector<vector<bool>> visited;

bool cmp(int a, int b) {
	return a > b;
}

void Input() {
	cin >> N >> M;
	arr.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		arr[i].resize(M);
		visited[i].resize(M, false);
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> arr[i][k];
		}
	}
}
bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void DFS(int sero,int garo, int count, int allSum) {
	visited[sero][garo] = true;
	allSum += arr[sero][garo];
	
	if (count == 4) {
		if (resultMax < allSum) {
			resultMax = allSum;
		}
		visited[sero][garo] = false;
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nextSero = sero + dy[i];
		int nextGaro = garo + dx[i];
		if (isInside(nextSero, nextGaro) == false)continue;
		if (visited[nextSero][nextGaro] == true)continue;
		DFS(nextSero, nextGaro, count + 1,allSum);
		visited[nextSero][nextGaro] = false;
	}
	visited[sero][garo] = false;
}
void SpecialCase(int sero, int garo) {
	
	
	Node up = { sero - 1,garo };
	Node right = { sero,garo + 1 };
	Node left = { sero,garo - 1 };
	Node down = { sero + 1,garo };
	vector<Node> vec = { up,right,left,down };
	vector<int> numTank;
	numTank.resize(4, 0);

	int count = 0;
	for (int i = 0; i < 4; i++) {
		if (isInside(vec[i].first, vec[i].second)==false) {
			count++;
			continue;
		}
		numTank[i] = arr[vec[i].first][vec[i].second];
	}
	if (count >= 2)return;

	sort(numTank.begin(), numTank.end(), cmp);
	int sum = arr[sero][garo];
	for (int i = 0; i < 3; i++) {
		sum += numTank[i];
	}

	if (resultMax < sum) {
		resultMax = sum;
	}


}

void Print() {
	cout << "\n";
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cout << visited[i][k] << " ";
		}
		cout << '\n';
	}
	cout << "\n";
}

void GameStart() {
	
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			DFS(i, k,1,0);
			SpecialCase(i, k);
		}
	}
	cout << resultMax;
}



int main(void) {
	Input();
	
	GameStart();

}