[알고리즘] 백준 14500번: 테트로미노 (C++), 좋은 문제였다

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

14500번: 테트로미노

이번 문제는 논리도 한 번에 나오고, 구현에도 막힘이 없었고, 반례도 스스로 찾아 넣으면서 엄청 성취감을 줬던 문제다.

다음 도형에서 보라색을 제외한 4가지 도형은 DFS로 구할 수 있지만 보라색은 BFS로 하기엔 번거로워서 아이디어를 내서 구현했다.

즉, 이 문제에서는 4가지 도형과 보라색 도형을 따로 구분할 줄 아는 분석력과 보라색 도형의 경우를 구현하는 능력을 필요로 한다.

---

DFS로 생각했던 이유

보라색을 제외한 4가지 도형은 4가지 방향(상, 하, 좌, 우)을 고려하여 경로를 4칸 이동하는 경우의 수들과 같은 형태를 보인다. 도형이 대칭이 될 수도 있고, 회전이 가능하기 때문에 DFS를 써도 되겠다는 결론이 났다. 다만, 보라색은 DFS로는 구할 수 없기에 보라색의 경우만 따로 구현을 하였다.

 

보라색의 경우

다음은 보라색 도형을 구현한 함수다. 기존 sum에는 항상 함수가 call 될 때의 map값(value)을 가지고 있으며 첫 번째 for문으로 3가지 방향을 골라낸다. 안에 속해있는 for문과 연관을 지어 3가지 방향을 고려하게 만들었다.

그리고, 무조건 3방향이 채택되어야 보라색 도형 모양이 되기 때문에 조건을 만족하지 않는 경우 다음 도형을 고려하는 경우로 코드를 작업했다.

void purple(int row, int col, int value) {
	int sum = value;

	for (int cnt = 0; cnt < 4; cnt++) { 
    // 3가지 방향을 고려하기 때문에
	// 한번 수행할 때 한 방향은 제거 해야함
		for (int i = 0; i < 4; i++) {
			if (i == cnt) {
            // 1 2 3, 0 2 3, 0 1 3, 0 1 2
				continue;
			}
			int dy = row + dir[i].y;
			int dx = col + dir[i].x;
			if (dy < 1 || dy > n || dx > m || dx < 1) {
			// 다음 조건을 만족한다면 3가지 방향이 나오지 않음
				sum = value;
				break;
			}
			sum += map[dy][dx];
		}
		if (sum > maxValue) {
			maxValue = sum;
		}
		sum = value;
	}
}

보라색을 구현하는 데에 오류가 났었었다. if문 조건에서 (dy < 1 || dy > n || dx > m || dx < 1)를 &&(AND)로 했었어서 오류(틀렸습니다)가 났었다. 논리 연산자 오류 부분 정말 가끔 있는 오류라 오류인지 잘 파악을 못 한다. 평소에는 참인 조건으로 if문을 걸기 때문에 반대의 조건을 달 일이 생기면 항상 체크해야 하는 부분이다.

---

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int n, m;
int map[501][501];
bool visited[501][501];
int maxValue = 0;

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void dfs(int row, int col, int cnt, int sum) {
// 보라색을 제외한 다른 4가지의 경우
	if (cnt == 4) {
		if (sum > maxValue) {
			maxValue = sum;
		}
		return;
	}

	for (int i = 0; i < 4; i++) {
		int dy = row + dir[i].y;
		int dx = col + dir[i].x;
		if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
			if (!visited[dy][dx]) {
				visited[dy][dx] = 1;
				dfs(dy, dx, cnt + 1, sum + map[dy][dx]);
				visited[dy][dx] = 0;
			}
		}
	}
}

void purple(int row, int col, int value) {
	int sum = value;

	for (int cnt = 0; cnt < 4; cnt++) {
    // 3가지 방향을 고려하기 때문에
	// 한번 수행할 때 한 방향은 제거 해야함
		for (int i = 0; i < 4; i++) {
			if (i == cnt) {
            // 1 2 3, 0 2 3, 0 1 3, 0 1 2
				continue;
			}
			int dy = row + dir[i].y;
			int dx = col + dir[i].x;
			if (dy < 1 || dy > n || dx > m || dx < 1) {
				// 다음 조건을 만족한다면 3가지 방향이 나오지 않음
				sum = value;
				break;
			}
			sum += map[dy][dx];
		}
		if (sum > maxValue) {
			maxValue = sum;
		}
		sum = value;
	}
}

int main() {
	cin >> n >> m;
	int idx;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> idx;
			map[i][j] = idx;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!visited[i][j]) {
				visited[i][j] = 1;
				dfs(i, j, 1, map[i][j]);
				visited[i][j] = 0;
			}
			purple(i, j, map[i][j]);
		}
	}

	cout << maxValue;
	return 0;
}