[백준 14500] 테트로미노 (C++) - G4

문제

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

14500번: 테트로미노

 

개요

이 문제는 구현 문제이다.

위의 5가지 종류의 테트로미노가 주어지는데, 회전과 대칭이 가능하기 때문에 가능한 모양은 5개가 아니라 사실상 총 19개가 나온다.

19가지 경우를 모두 하나하나 구현해야하는 것인가 하고 굉장히 막막했다.

그러던 중에 DFS + 백트래킹을 이용하면 더욱 쉽게 풀 수 있음을 알게 되었다.

 

문제 풀이

위에서 언급했던 총 19가지 모양에 대해 각각 if문을 구현하여 총 19개의 if문을 포함하는 함수를 구현할 수도 있을 것이다.

그러나, 이와 같은 방법은 중간에 실수할 가능성도 크고 중간에 코드를 잘못 적었으면 찾기도 힘들 것이다.

 

이 문제는 DFS + 백트래킹을 이용하여 더 간단하게 풀 수 있다.

왜 DFS를 사용할 수 있는 것일까?

다음 그림을 보자.

5가지 모양 중에 'ㅜ' 모양을 제외한 나머지 4개의 모양은 Depth가 3인 도형임을 확인할 수 있다.

즉, 다음과 같이 한 좌표에 대해서 Depth가 3인 DFS를 실행하면, 해당 좌표를 기준으로 한 4개의 모양(회전, 대칭 포함)에 대한 합을 각각 구할 수 있다. (아래 그림에서 검은 동그라미가 기준 좌표이다.)

DFS를 통해 Depth = 3까지 타고 들어가서 지나온 좌표에 저장된 숫자의 합을 구하는 방식으로 진행한다.

여기서 중요한 점은, 한 좌표에 대해서 Depth = 3으로 타고 들어가는 방법은 여러 경우가 있기 때문에 백트래킹(Backtracking)을 사용하여 여러 경우에서의 숫자의 합을 모두 구하면서 최종적으로 가장 큰 합을 구해야 한다.

 

그리고 'ㅜ' 모양에 대해서는 DFS를 사용하여 구할 수 없기 때문에 따로 if문을 통해 구현해주어야 한다.

(그림에서 검은 동그라미는 기준이 되는 좌표이다.)

위의 4가지 모양에 대해서 if문을 구현하여 총 4개의 if문을 가진 ohshape 함수를 따로 작성해주었다.

 

 

코드

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

#define INF (~0U >> 2) // 약 10억 7천만 (1073741823)

using namespace std;

int n, m, ans;
int arr[500][500];
int visited[500][500];
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };

// ㅗ 모양 따로 처리 (대칭, 회전 고려)
void ohshape(int y, int x) {

	// ㅜ
	if (y + 1 < n && x + 2 < m)
		ans = max(ans, arr[y][x] + arr[y][x + 1] + arr[y][x + 2] + arr[y + 1][x + 1]);
	// ㅏ
	if (y + 2 < n && x + 1 < m)
		ans = max(ans, arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y + 1][x + 1]);
	// ㅗ
	if (y - 1 >= 0 && x + 2 < m)
		ans = max(ans, arr[y][x] + arr[y][x + 1] + arr[y][x + 2] + arr[y - 1][x + 1]);
	// ㅓ
	if (y + 2 < n && x - 1 >= 0)
		ans = max(ans, arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y + 1][x - 1]);
}

// DFS + Backtracking
void dfs(int y, int x, int sum, int depth) {

	if (depth == 3) {
		ans = max(ans, 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) continue;

		if (visited[ny][nx] == 0) {
			visited[ny][nx] = 1;
			dfs(ny, nx, sum + arr[ny][nx], depth + 1);
			visited[ny][nx] = 0;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ohshape(i, j);
			visited[i][j] = 1;
			dfs(i, j, arr[i][j], 0);
			visited[i][j] = 0;
		}
	}

	cout << ans;
	return 0;
}

 

깨달은 점

구현 문제는 무식하게 모든 경우를 일일이 나눠서 코드를 작성해야 하는 줄 알았다.

그러나, 이 문제와 같이 구현 문제에서도 DFS + 백트래킹을 사용하면 코드가 훨씬 간결해지는 것을 알게 되었다.

구현 문제를 풀 때, 문제 설명을 읽은 후에 해당 문제가 DFS 또는 백트래킹을 사용하여 접근할 수 있는지를 얼마나 빨리 판단하는지가 중요할 것 같다.