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

[youbeen2798]

문제 링크 : https://www.acmicpc.net/problem/14500
문제 난이도 : 골5
풀이 : 완전 탐색 기반 DFS 사용

• DFS 라는 풀이를 알아도, 풀이 방식이 익숙치 않다면 헷갈릴만한 문제

<풀이 과정>
문제가 정의한 테트로미노의 모양(하나 제외)들은 한 점에서 DFS를 통해 depth 4까지 탐색하는 모든 경로와 같음

한가지 예외: ㅗ,ㅓ,ㅏ,ㅜ의 모양은 배열의 각 원소마다 직접 더하는 방법밖에 없음( ㅗ,ㅓ,ㅏ,ㅜ의 모양은 depth가 4가 아닌 3이기 때문)

• 각 테트로미노들의 합의 최댓값을 answer이라고 정의

#include <iostream>

using namespace std;

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

int answer = 0;

bool visited[501][501] = { false, };
int arr[501][501];

bool isIn(int r, int c) { //범위를 넘는지 안 넘는지 확인
	if (r < 0 || r >= n || c < 0 || c >= m) {
		return false;
	}
	return true;
}

void dfs(int r, int c, int depth, int sum) { //
	if (depth == 3) { //depth가 3이라면 테트로미노 완성
		answer = max(answer, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nR = r + dx[i];
		int nC = c + dy[i];

		if (isIn(nR, nC) == false) {
			continue;
		}
		if (visited[nR][nC] == true) {
			continue;
		}
		visited[nR][nC] = true;
		dfs(nR, nC, depth + 1, sum + arr[nR][nC]);
		visited[nR][nC] = false;
	}
}

void solu1(int r, int c) { //모양이 ㅏ
	int sum = 0;
	sum = arr[r][c] + arr[r + 1][c] + arr[r + 2][c] + arr[r + 1][c + 1];

	answer = max(answer, sum);
}

void solu2(int r, int c) { //모양이 ㅗ
	int sum = 0;
	sum = arr[r][c] + arr[r][c + 1] + arr[r][c + 2] + arr[r - 1][c + 1];
	answer = max(answer, sum);
}

void solu3(int r, int c) { //모양이 ㅜ
	int sum = 0;
	sum = arr[r][c] + arr[r][c + 1] + arr[r][c + 2] + arr[r + 1][c + 1];
	answer = max(answer, sum);
}

void solu4(int r, int c) { //모양이 ㅓ
	int sum = 0;
	sum = arr[r][c] + arr[r][c + 1] + arr[r - 1][c + 1] + arr[r + 1][c + 1];
	answer = max(answer, sum);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	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++) {
			visited[i][j] = true;
			dfs(i, j, 0, arr[i][j]);
			visited[i][j] = false;

			if (i < n - 2 && j < m - 1) {
				solu1(i, j);
			}
			if ( 0<i && j < m - 2) {
				solu2(i, j);
			}
			if (i < n - 1 && j < m - 2) {
				solu3(i, j);
			}
			if ( 0< i && i < n - 1 && j < m - 1) {
				solu4(i, j);
			}
		}
	}

	cout <<  answer;
}