<C/C++> BOJ 14500: 테트로미노

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 500
int N, M;
int sol, mx;
int map[MAXN + 10][MAXN + 10];
int visited[MAXN + 10][MAXN + 10];
static int dr[] = { -1, 1, 0, 0 };
static int dc[] = { 0, 0, -1, 1 }; 
static int tet[][3] = { {0, 1, 2}, {1, 2, 3}, {0, 1, 3}, {0, 2, 3} };

void Input(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (mx < map[i][j]) mx = map[i][j];
		}
	}
}
void DFS(int r, int c, int t, int sum) {
	int nr, nc;
	if (t >= 4) {
		if (sol < sum) sol = sum;
		return;
	}
	if (sol >= mx*(4 - t) + sum) return;
	for (int i = 0; i < 4; i++) {
		nr = r + dr[i], nc = c + dc[i];
		if (visited[nr][nc]) continue;
		if (nr >= N || nr < 0 || nc >= M || nc < 0) continue;
		visited[nr][nc] = 1;
		DFS(nr, nc, t + 1, sum + map[nr][nc]);
		visited[nr][nc] = 0;
	}
}

void check() {
	int sum, nr, nc, dir;
	for (int i = 0; i < N; i++) { //효율 높이려고 범위 줄였다가 테케 통과도 못하게 너무 줄임
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < 4; k++) {
				sum = map[i][j];
				for (int idx = 0; idx < 3; idx++) {
					dir = tet[k][idx];
					nr = i + dr[dir], nc = j + dc[dir];
					if (nr >= N || nr < 0 || nc >= M || nc < 0) break;
					sum += map[nr][nc];
				}
				if (sol < sum) sol = sum;
			}
		}
	}
}
int main(void) {
	Input();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = 1;
			DFS(i, j, 1, map[i][j]);
			visited[i][j] = 0;
		}
	}
	check();
	cout << sol << endl;
	return 0;
}

 DFS 사용
 단 'ㅜ'모양은 DFS로 할 방법 못찾겠어서 예외로 check 함수 만들었음
 여기서 효율 높이려다가 범위 조정 실수함. 에지케이스들 잘 잡아내자!