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

www.acmicpc.net/problem/14500

14500번: 테트로미노

---

 

 

-풀이-

일반적인 dfs로 깊이를 4까지 내려가면, ㅗ 모양을 제외하고 해당 i,j를 기준으로 범위를 벗어나지 않는 모든 모양을 만들 수 있다.

따라서 dfs로 4개까지의 합을 모두 구한다음에 최댓값을 갱신해준뒤, ㅗ모양을 따로 체크하는 함수를 만들어서 ㅗ에따른 최댓값을 따로 갱신시켜주면 된다.

 

-시간복잡도-

모든 배열을 dfs로 돌아다니므로 O(N*N) 이 된다.

 

-코드-

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

int maze[500][500];
int n,m;
int answer = 0;
int mv[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
bool visited[500][500];

bool isIn(int i, int j) {
	return i >= 0 && i < n&&j >= 0 && j < m;
}

void fu(int i, int j) {
	if (isIn(i , j+1) && isIn(i - 1, j) && isIn(i , j-1)) {
		answer = max(answer, maze[i - 1][j] + maze[i][j - 1] + maze[i][j] + maze[i][j + 1]);
	}

	if (isIn(i, j + 1) && isIn(i + 1, j) && isIn(i, j - 1)) {
		answer = max(answer, maze[i + 1][j] + maze[i][j - 1] + maze[i][j] + maze[i][j + 1]);
	}

	if (isIn(i - 1, j) && isIn(i + 1, j) && isIn(i, j + 1)) {
		answer = max(answer, maze[i - 1][j] + maze[i + 1][j] + maze[i][j] + maze[i][j + 1]);
	}
	if (isIn(i - 1, j) && isIn(i + 1, j) && isIn(i, j - 1)) {
		answer = max(answer, maze[i - 1][j] + maze[i + 1][j] + maze[i][j] + maze[i][j - 1]);
	}
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> maze[i][j];
}

void dfs(int i, int j,int sum,int cnt) {
	if (cnt == 4) {
		answer = max(answer, sum);
		return;
	}
	for (int d = 0; d < 4; d++) {
		int ni = i + mv[d][0];
		int nj = j + mv[d][1];

		if (isIn(ni, nj) && !visited[ni][nj]) {
			visited[ni][nj] = true;
			dfs(ni, nj, sum + maze[ni][nj],cnt+1);
			visited[ni][nj] = false;
		}
	}
}

void solve() {

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j]) {
				visited[i][j] = true;
				dfs(i, j, maze[i][j], 1);
				fu(i, j);
				visited[i][j] = false;
			}
		}
	}

	cout << answer << "\n";
}

int main() {
	input();
	solve();
}