[BOJ] 14500 테트로미노

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

14500번: 테트로미노

 

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

struct POS
{
	int y, x, value;
};

int n, m, res;
int arr[501][501];

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

vector <POS> v; // for DFS
bool visit[501][501] = {false};


// DFS
void DFS() {

	if(v.size() == 4) {
		int answer = 0;
		for(int i=0; i<int(v.size()); i++) {
			answer += v[i].value;
		}
		res = max(res, answer);
		return;
	}

	// ㅗ ㅏ ㅜ ㅓ 때문에
	for(int k=0; k<int(v.size()); k++) {
		int cy = v[k].y;
		int cx = v[k].x;
	
		// 2. check each v ele.
		for(int i=0; i<4; i++) {
			POS next;
			next.y = cy + dy[i];
			next.x = cx + dx[i];
			next.value = arr[next.y][next.x];

			if(next.y < 0 || next.y >= n || next.x < 0 || next.x >=m) continue;
			if(visit[next.y][next.x]) continue;
			visit[next.y][next.x] = true;
			v.push_back(next);
			DFS();
			v.pop_back();
			visit[next.y][next.x] = false;
		}
	}

	return;
}


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

	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++) 
			scanf("%d" ,&arr[i][j]);


	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++) {
			v.clear();
			POS tmp;
			tmp.y = i; tmp.x = j; tmp.value = arr[i][j];
			v.push_back(tmp); // put first ele
			visit[i][j] = true;
			DFS();
			visit[i][j] = false;
		}

	printf("%d\n", res);
	return 0;
}

 

ㅗ ㅜ ㅓ ㅏ 를 제외한 4개블록으로 이뤄진 블록을 구하는 것이라면 일반적인 DFS 가 가능하겠지만

ㅗ ㅜ ㅓ ㅏ 다시 생각을 해줘야한다.

 

일반적인 DFS 를 사용하여 연속된 4개의 블록을 구하여 vector v 에 저장하는 점은 동일하다.

하지만 가장 마지막에 저장된 vector v 의 값이 시작점이 아닐 수도 있다!

 

4 4

0 1 4 2

0 0 3 0

0 0 0 0

0 0 0 0

 >> ANS : 10 

 

그렇기 때문에 v 에 들어있는 모든 원소들을 한번씩 확인을 더 해주자. DFS() 에 이중 for 문을 쓴 이유!

그렇게 쓰지 않는다면 따로 ㅗ ㅜ ㅓ ㅏ 를 확인해주는 함수를 생성하는 방법이 있다. (속도는 더 빠름. 하지만 구현 실수가 잦아서 하다가 말아버림)

 

이중 for 문을 사용하기는 했지만 visit 체크에 걸려 속도에 걸리지는 않는다.