[백준 14500번 - 테르로미노] C++ 풀이

백준 14500번.

 

사용한 알고리즘

- bfs

 

depth 가 4로 정해져있으니 bfs 풀어야겠다는 생각이 들었다. 그리고 테스트 해보니 빠뜨린게 있었는데..! ㅜ/ㅗ/ㅓ/ㅏ 모양은 따로 값을 계산해서 최대값인지를 체크해주어야 한다.

bfs 를 위한 visited 배열을 만들었는데, 해당 배열을 dfs 함수의 인자로 넣어주니까 시간초과가 계속 나더라..(call by reference 로 해도..) 그래서 없애고 전역변수로 줬더니 맞았다. 그래도 시간이 빠듯한듯. dfs 풀면 대략 500 * 500 * 4 ^ 4 정도의 시간복잡도가 된다.

 

완성된 코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;
int n, m;
vector<vector<int>> v;
vector<vector<bool>> visited;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int ans = 0;

void dfs(int x, int y, int depth, int result) {
	if (depth == 3) {
		ans = (ans < result) ? result : ans;
		return;
	} else {
		for(int i = 0; i < 4; ++i) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny])
				continue;
			else {
				visited[nx][ny] = true;
				dfs(nx, ny, depth + 1, result + v[nx][ny]);
				visited[nx][ny] = false;
			}
		}
		return;
	}
}

int main() {
	scanf("%d %d", &n, &m);

	v.assign(n + 1, vector<int>(m + 1));
	visited.assign(n + 1, vector<bool>(m + 1, false));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			scanf("%d", &v[i][j]);
		}
	}

	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			visited[i][j] = true;
			dfs(i, j, 0, v[i][j]);
			visited[i][j] = false;
			int temp = 0;
			if (i - 1 >= 0 && i + 1 < n && j - 1 >= 0) {
				temp = v[i][j] + v[i - 1][j] + v[i + 1][j] + v[i][j - 1];
				if (temp > ans)
					ans = temp;
			}
			if (i - 1 >= 0 && i + 1 < n && j + 1 < m) {
				temp = v[i][j] + v[i - 1][j] + v[i + 1][j] + v[i][j + 1];
				if (temp > ans)
					ans = temp;
			}
			if (i - 1 >= 0 && j + 1 < m && j - 1 >= 0) {
				temp = v[i][j] + v[i - 1][j] + v[i][j - 1] + v[i][j + 1];
				if (temp > ans)
					ans = temp;
			}
			if (i + 1 < n && j + 1 < m && j - 1 >= 0) {
				temp = v[i][j] + v[i + 1][j] + v[i][j - 1] + v[i][j + 1];
				if (temp > ans)
					ans = temp;
			}
		}
	}
	printf("%d\n",ans);
}