백준 14500 테트로미노

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

 

서론

정사각형 4개가 가질 수 있는 모든 경우의 수를 찾기 위해 DFS를 이용했는데

보라색 사각형 모양이 DFS로는 안나온다. 이걸 구현한 후에야 알았다.

접근법이 틀렸다고 생각해서 이것저것 생각해봤는데

저 모양의 사각형들을 일일이 만들어야 하는것만 떠올랐다. 

그리고 다른분의 풀이를 봤더니 보라색 사각형만 만들고 나머지는 DFS로 구현했다. 왜 이걸 생각하지 못했을까

 

---

풀이

보라색을 제외한 나머지는 DFS로 구현한다.

DFS는 전형적인 DFS이며 깊이가 4가되면 탐색한 칸들의 합을 최대값과 비교하고 리턴한다.

탐색한 칸들의 합은 DFS의 인수에 더해주는 방식을 이용한다.

void dfs(int y, int x, int sum) {
	sum += map[y][x];
	if (깊이 == 4) {
		result = max(result, sum);
		return;
	}
	dfs(nexty, nextx, sum);
	return;
}

 

이를 모든 칸에 실행한다.

그리고 보라색 사각형도 특정 칸과 상하좌, 상하우, 상좌우, 하좌우에 해당하는 값들을 더하여 출력하는 함수를 만들고 DFS로 얻어진 최대값과 비교한다.

int main() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// 모든 칸에 대해서 dfs와 purple를 실행함
			// sum는 map[i][j]를 포함한 테트로미노 중 최대값을 가져야 함
			sum = max(dfs(i, j, 0), purple(i, j)); // 보라색 사각형은 purple로 얻어지며 나머지 사각형들은 dfs로 얻어짐
			result = max(sum, result)
		}
	}
	cout << result;

}

 

---

구현

// c++

#include <iostream>
#include <algorithm>

using namespace std;

int result;
int n, m;
int map[501][501];
int visited[500][500];

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

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

int purple(int y, int x) {
	int sum = 0;
	int tmp = 0;
	tmp = map[y - 1][x] + map[y][x + 1] + map[y][x - 1] + map[y][x];
	sum = max(tmp, sum);

	tmp = map[y + 1][x] + map[y][x + 1] + map[y][x - 1] + map[y][x];
	sum = max(tmp, sum);

	tmp = map[y + 1][x] + map[y - 1][x] + map[y][x - 1] + map[y][x];
	sum = max(tmp, sum);

	tmp = map[y + 1][x] + map[y - 1][x] + map[y][x + 1] + map[y][x];
	sum = max(tmp, sum);

	return sum;
}

void dfs(int y, int x, int sum) {
	sum += map[y][x];
	if (visited[y][x] == 4) {
		/*
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) cout << visited[i][j];
			cout << endl;
		}
		cout << sum << endl;
		*/
		result = max(result, sum);
		return;
	}
	
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 0 && nx >= 0 && ny < n && nx < m && visited[ny][nx] == 0) {
			visited[ny][nx] = visited[y][x] + 1;
			dfs(ny, nx, sum);
			visited[ny][nx] = 0;
		}
	}
	return;
}

int main() {
	init();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = 1;
			dfs(i, j, 0);
			visited[i][j] = 0;
			result = max(result, purple(i, j));

		}
	}

	cout << result;

}