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

이 포스트는 백준 사이트의 테트로미노 문제 풀이입니다.

문제

해결 과정

문제를 풀기 전 먼저 전체 과정을 어떻게 해결할지 순서를 정했습니다.

1. 입력
2. 탐색
3. 위치 유효성 확인 (테트로미노인지 확인)
4. 최댓값 갱신

각 과정을 모두 함수로 분리하고 전역 변수는 최소한으로 하기 위해
1~4 번 함수 모두가 사용하는 변수만 전역 변수로 승격했습니다.

그 다음 탐색 방법은 모든 위치를 방문해 테트로미노를 확인하는 탐색 외 다른 방법이 있는지 고민했지만
뾰족한 수가 없다고 판단하여 각 위치에서 탐색을 사용하기로 하였습니다.

각 위치에서는 완전탐색과 깊이우선탐색 으로 ‘ㅜ’ 모양과 그 외의 모양을 탐색하였습니다.

‘ㅜ’ 모양을 구분한 이유는 그 외의 모양들은 한 위치에서 되돌아올 필요 없이
깊이우선탐색 으로 확인 가능한 경로들이지만 ‘ㅜ’ 모양은 반드시 한 번은 되돌아와야 하기 때문에
깊이우선탐색이 아닌 완전탐색 을 사용했습니다.

코드 구현

#include <iostream>

using namespace std;

int** board;
bool** visited;
int N, M;
int dir_row[4]{-1, 1, 0, 0};
int dir_col[4]{0, 0, -1, 1};

void input(int& N, int& M);
void find_special_shape(int row, int col, int& answer);
void find_normal_shape(int row, int col, int& answer, int length, int sum);
void search_board(int row, int col, int& answer);
void solution(int& N, int& M, int& answer);

int main() {
	int answer = 0;
	
	input(N, M);
	solution(N, M, answer);
	printf("%d", answer);

	delete board;
	return 0;
}

void input(int& N, int& M) {
	cin.tie(0)->sync_with_stdio(false);
	cout.tie(0);

	cin >> N >> M;
	
	board = new int*[N];
	visited = new bool*[N];

	for(int row = 0; row < N; ++row) {
		visited[row] = new bool[M];
		fill(visited[row], visited[row] + M, false);

		board[row] = new int[M];
		for(int col = 0; col < M; ++col) {
			cin >> board[row][col];
		}
	}
}

void solution(int& N, int& M, int& answer) {	
	for(int row = 0; row < N; ++row) {
		for(int col = 0; col < M; ++col) {
			search_board(row, col, answer);
		}
	}	
}

void search_board(int row, int col, int& answer) {
	find_special_shape(row, col, answer);

	visited[row][col] = true;
	find_normal_shape(row, col, answer, 1, board[row][col]);
	visited[row][col] = false;
}

void find_special_shape(int row, int col, int& answer) {
	// ㅓ
	if (row + 1 < N && col + 2 < M) {
        answer = max(answer, board[row][col] + board[row][col + 1] + board[row][col + 2] + board[row + 1][col + 1]);
	}
    // ㅏ
    if (row + 2 < N && col + 1 < M) {
        answer = max(answer, board[row][col] + board[row + 1][col] + board[row + 1][col + 1] + board[row + 2][col]);
	}
    // ㅗ
    if (row - 1 >= 0 && col + 2 < M) {
        answer = max(answer, board[row][col] + board[row][col + 1] + board[row][col + 2] + board[row - 1][col + 1]);
	}
    // ㅓ
    if (row + 2 < N && col - 1 >= 0) {
        answer = max(answer, board[row][col] + board[row + 1][col] + board[row + 1][col - 1] + board[row + 2][col]);
	}
}

void find_normal_shape(int row, int col, int& answer, int length, int sum) {
	if(length == 4) {
		answer = max(answer, sum);
		return;
	}

	for(int dir_idx = 0; dir_idx < 4; ++dir_idx) {
		int new_row = row + dir_row[dir_idx];
		int new_col = col + dir_col[dir_idx];

		if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= M) {
			continue;
		}
		if(visited[new_row][new_col]) {
			continue;
		}

		visited[new_row][new_col] = true;
		find_normal_shape(new_row, new_col, answer, length + 1, sum + board[new_row][new_col]);
		visited[new_row][new_col] = false;
	}	
}

실행 결과