[백준] 14500번 테트로미노 C++ 코드

코드1 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
int n, m, a[503][503],res, visited[503][503];
vector<pair<int, int>> v;

// 전략 -> 완탐, 원복을 통해 값 찾기
// ㅗ모양은 따로 찾아주어야 한다.

void go(int x, int y, int cnt) {
	if (cnt == 4) {
		int tmp = 0;
		for (pair<int, int> pa : v) {
			tmp += a[pa.first][pa.second];
		}
		res = max(res, tmp);
        
        // ㅗ모양 찾기
		int o = v[0].first;
		int t = v[0].second;
		// 하 상 우 좌

		for (int i = 0; i < 4; i++) {
			int tmpf = 0;
			int nx = o + dx[i];
			int ny = t + dy[i];
			if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
            // 아래로 간 경우는 왼쪽 오른쪽에 붙여줌
			if (i == 0) {
				int left = ny - 1;
				int right = ny + 1;
				if (left >= m || left < 0 || right >= m || right < 0) continue;
				tmpf = a[o][t] + a[nx][ny] + a[nx][left] + a[nx][right];
			}
            // 위로 간 경우는 왼쪽 오른쪽에 붙여줌
			else if(i == 1) {
				int left = ny - 1;
				int right = ny + 1;
				if (left >= m || left < 0 || right >= m || right < 0) continue;
				tmpf = a[o][t] + a[nx][ny] + a[nx][left] + a[nx][right];
			}
            // 오른쪽으로 간 경우는 위 아래에 붙여줌
			else if (i == 2) {
				int up = nx - 1;
				int down = nx + 1;
				if (up >= n || up < 0 || down >= n || down < 0) continue;
				tmpf = a[o][t] + a[nx][ny] + a[up][ny] + a[down][ny];
			}
            // 왼쪽으로 간 경우는 위 아래에 붙여줌
			else if (i == 3) {
				int up = nx - 1;
				int down = nx + 1;
				if (up >= n || up < 0 || down >= n || down < 0) continue;
				tmpf = a[o][t] + a[nx][ny] + a[up][ny] + a[down][ny];
			}
			res = max(res, tmpf);
		}
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= n || nx < 0 || ny >= m || ny < 0 || visited[nx][ny]) continue;
		visited[nx][ny] = 1;
		v.push_back({ nx, ny });
		go(nx, ny, cnt + 1);
		visited[nx][ny] = 0;
		v.pop_back();
	}
	return;
}
void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
int main() {
	FASTIO();
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = 1;
			v.push_back({ i, j });
			go(i, j, 1);
			visited[i][j] = 0;
			v.pop_back();
		}
	}
	cout << res << '\n';
	return 0;
}

코드2 (시간효율성 코드 1보다 낮음)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

int n, m, a[503][503], res, visited[503][503];
vector<pair<int, int>> v;

void go(int x, int y ,int cnt) {
	if (cnt == 4) {
		int tmp = 0;
		for (pair<int, int> pa : v) {
			tmp += a[pa.first][pa.second];
		}
		res = max(res, tmp);
        // ㅗ모양 찾아주기
        // 3개가 연결된 상태에서 나머지 1개를 각각 칸에서 추가하여 탐색
        // 불필요한 탐색이 많아 시간이 더 오래걸리는 듯함
		for (int i = 0; i < 3; i++) {
			int nx = v[i].first;
			int ny = v[i].second;
			for (int j = 0; j < 4; j++) {
				int nnx = nx + dx[j];
				int nny = ny + dy[j];
				if (nnx >= n || nny >= m || nnx < 0 || nny < 0 || visited[nnx][nny]) continue;
				tmp = a[nnx][nny] + a[v[0].first][v[0].second] + a[v[1].first][v[1].second] + a[v[2].first][v[2].second];
				res = max(res, tmp);
			}
		}
		return;
	}
  
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= n || ny >= m || nx < 0 || ny < 0 || visited[nx][ny]) continue;
		visited[nx][ny] = 1;
		v.push_back(make_pair(nx, ny));
		go(nx, ny, cnt + 1);
		visited[nx][ny] = 0;
		v.pop_back();
	}
	return;
}

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	FASTIO();
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			go(i, j, 0);
		}
	}
	cout << res << '\n';
	return 0;
}

풀이

텀을 두고 풀어서 ㅗ모양 찾는 풀이 방법이 조금 다르다. 우선 테트로미노 모양을 보면 4개가 연속으로 이어붙어 있어 그래프 탐색으로 찾을 수 있을 거라 생각했다. 그런데 3번 케이스에서 ㅏ 모양을 고려하지 않았다는 것을 알았고 따로 만들어야 겠다고 생각했다.

 

1번 풀이의 경우는 첫번째 요소에서 출발해서 2번째 요소가 어떤 방향으로 가느냐에 따라 ㅏ 모양을 만들어 주었다. 2번 풀이의 경우는 3개가 이어붙어 있는 상태에서, 1개 요소마다 상하좌우에 붙여보고 확인을 했다. 아마 불필요한 탐색도 포함되었기 때문에 시간이 더 오래 걸린 것으로 추정된다.