C++ / 백준 / 14500 / 테트로미노

문제

 

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

14500번: 테트로미노

 

 

문제풀이

 

문제를 대충 봤을 때는 블록을 이리저리 회전하고, 대칭시켜서 모든 칸을 확인해야 되나 싶었다.

문제를 자세히 보니 5가지 블록은 모두 4칸으로 되어있고, 5가지를 제외하고 4칸으로 표현할 수 있는 블록이 더 있을까 생각을 해봤는데 당장 떠오르는 모양이 없었다.

그래서 모든 칸에서 DFS를 돌려 모든 경우를 탐색해 보면 되겠다 싶었다.

 

DFS함수는 인자로 y, x, 그리고 현재 탐색한 블록 개수, 블록 값들의 합을 갖는다.

개수가 4개가 되면 answer의 값과 비교하여 더 큰 값을 갖게 한다.

개수가 4개가 되지 않으면 새로 갈 좌표의 위치를 구하고, 범위를 벗어나는지, 이미 방문했는지를 확인한다.

방문을 하지 않았다면 방문표시를 하고 다시 DFS함수를 돌린다.

 

코드를 다 작성하고 예제들을 다 넣고 실행해 봤는데 예제 3에서 원하는 출력이 나오지 않았다.

문제를 다시 본 결과 분홍색 블록이 내가 짠 DFS로는 만들 수 없다는 것을 깨달았다.

그래서 DFS함수가 모두 끝났을 때, 따로 분홍색 블록들만 탐색하게끔 코드를 추가로 작성했다.

 

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			int sum(0);
			sum += board[y][x];

			if (y - 1 >= 0)	sum += board[y - 1][x];
			if (y + 1 < N)	sum += board[y + 1][x];
			if (x - 1 >= 0)	sum += board[y][x - 1];
			if (x + 1 < M)	sum += board[y][x + 1];

			if (y - 1 >= 0) answer = max(answer, sum - board[y - 1][x]);
			else answer = max(answer, sum);

			if (y + 1 < N) answer = max(answer, sum - board[y + 1][x]);
			else answer = max(answer, sum);

			if (x - 1 >= 0) answer = max(answer, sum - board[y][x - 1]);
			else answer = max(answer, sum);

			if (x + 1 < M) answer = max(answer, sum - board[y][x + 1]);
			else answer = max(answer, sum);
		}
	}

언뜻 보면 길지만 내용은 간단하다.

현재 y, x칸을 기준으로 주변의 칸을 모두 더한다.

 

만약 주변칸을 모두 더했으면 5칸을 더한 상태가 된다.

따라서 한 칸씩 제거해 주면서 answer값을 최댓값으로 갱신해 준다.

 

y, x가 구석이라면 3칸이 더해져 있는 상태일 것이다. 입력은 1,000을 넘지 않는 자연수이므로 이 부분은 의미가 없다.

(3칸으로는 최댓값이 될 수가 없고 현재 더해진 3칸은 DFS를 통해 완성된 블록의 일부가 되어있을 것이다.)

 

그 외의 경우는 4칸이다.

4칸은 각각의 else에 의해서 answer값을 갱신할 수가 있다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

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

vector<vector<int>>board;
vector<vector<bool>>visited;

void DFS(int y, int x, int cnt, int val) {
	if (cnt == 4) {
		answer = max(answer, val);		
		return;
	}
	for (int idx = 0; idx < 4; ++idx) {
		int ny = y + dy[idx];
		int nx = x + dx[idx];
		if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
		if (visited[ny][nx] == true) continue;
		visited[ny][nx] = true;
		DFS(ny, nx, cnt + 1, val + board[ny][nx]);
		visited[ny][nx] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	board = vector<vector<int>>(N, vector<int>(M, 0));
	visited = vector<vector<bool>>(N, vector<bool>(M, false));

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			cin >> board[y][x];
		}
	}

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			visited[y][x] = true;
			DFS(y, x, 1, board[y][x]);
			visited[y][x] = false;
		}
	}

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			int sum(0);
			sum += board[y][x];

			if (y - 1 >= 0)	sum += board[y - 1][x];
			if (y + 1 < N)	sum += board[y + 1][x];
			if (x - 1 >= 0)	sum += board[y][x - 1];
			if (x + 1 < M)	sum += board[y][x + 1];

			if (y - 1 >= 0) answer = max(answer, sum - board[y - 1][x]);
			else answer = max(answer, sum);

			if (y + 1 < N) answer = max(answer, sum - board[y + 1][x]);
			else answer = max(answer, sum);

			if (x - 1 >= 0) answer = max(answer, sum - board[y][x - 1]);
			else answer = max(answer, sum);

			if (x + 1 < M) answer = max(answer, sum - board[y][x + 1]);
			else answer = max(answer, sum);
		}
	}
	cout << answer;
}