[매일1문제] BOJ 14500 - 테트로미노

문제

[백준] 14500 - 테트로미노
시작 시간 : PM 5:53
아이디어 정리 : PM 5:57 / 구현 시작
구현 완료 시간 : PM 6:14 / 종료

아이디어

역시 완전탐색을 통해 해결이 가능한 문제였다.
‘ㅏ’형태를 띄는 테트로미노를 제외하고서는 모두 깊이가 4인 DFS를 돌리면 해결이 되므로, 그렇게 탐색하였다.
‘ㅏ’형태를 띄는 테트로미노는 따로 함수를 만들어 4가지 방향을 모두 시도해보는 방법을 사용했다.

구현

깊이가 4인 DFS는 매개변수를 통해 현재 깊이와 탐색한 경로의 가중치 합을 전달하였고, 깊이가 4일 때는 최댓값을 갱신하고 바로 리턴하였다.
‘ㅏ’형태를 띄는 테트로미노는 범위를 확인해 테트로미노를 만들 수 있다면 해당되는 필드의 값을 더한 값을 최댓값 갱신하였다.

결과

메모리 : 3260KB
시간 : 92ms
더 빠른 시간복잡도를 갖는 코드가 필요할 듯 하다.

소스코드

#include <bits/stdc++.h>
using namespace std;

const int dr[4] = { 1,-1,0,0 }, dc[4] = { 0,0,1,-1 };
int field[505][505], n, m, ans;
bool visited[505][505];

bool checkRange(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m;
}

void dfs(int x, int y, int dep, int cnt) {
	if (dep == 4) {
		ans = max(ans, cnt);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int r = x + dr[i], c = y + dc[i];
		if (!checkRange(r, c) || visited[r][c]) {
			continue;
		}
		visited[r][c] = true;
		dfs(r, c, dep + 1, cnt + field[r][c]);
		visited[r][c] = false;
	}
}

void ckT(int x, int y) {
	if (checkRange(x + 2, y + 1)) {
		int type1 = field[x][y] + field[x + 1][y] + field[x + 2][y] + field[x + 1][y + 1];
		int type2 = field[x][y + 1] + field[x + 1][y + 1] + field[x + 2][y + 1] + field[x + 1][y];
		ans = max(ans, max(type1, type2));
	}
	if (checkRange(x + 1, y + 2)) {
		int type1 = field[x][y] + field[x][y + 1] + field[x][y + 2] + field[x + 1][y + 1];
		int type2 = field[x + 1][y] + field[x + 1][y + 1] + field[x + 1][y + 2] + field[x][y + 1];
		ans = max(ans, max(type1, type2));
	}
}

int main(void) {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", field[i] + j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = true;
			dfs(i, j, 1, field[i][j]);
			ckT(i, j);
			visited[i][j] = false;
		}
	}
	printf("%d", ans);
	return 0;
}