백준 14500번 테트로미노 C/C++ 풀이

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

 

전형적인 DFS(깊이 우선 탐색, Depth-First Search) 문제이다.

 

DFS는 BFS(너비 우선 탐색, Breadth-First Search)와 구분되는데, 우선 각각의 개념을 알아보자

 

DFS란?

 

하나의 정점을 기준으로 그 지점에서 갈 수 있는 점들을 기준으로 탐색하는 방법이다.

글로 길게 적는 것보다 이에 대해 잘 설명하는 그림이 있어 들고 왔다.

출처는 https://twpower.github.io/151-bfs-dfs-basic-problem이다.

 

깊이 우선 탐색(DFS)

BFS란?

 

하나의 정점을 기준으로 그와 가까운 점들부터 탐색하는 것을 의미한다.

 

너비 우선 탐색(BFS)

문제에 제시된 테트로미노의 모양을 보면 깊이 탐색을 통해서 구현이 가능하다.

 

테트로미노

하지만 단 하나 ㅜ 모양의 테트로미노는 깊이 탐색으로 구현이 불가능하다. N번째 영역에서 N+1번째 영역으로 넘어갈 때 오른쪽이나 왼쪽 인접한 곳에 붙어있어야 하는데, 그렇지 않은 것을 알 수 있다.

 

ㅜ 모양의 테트로미노는 따로 구현을 해줘야 한다.

 

#include <cstdio>
#include <utility>

using namespace std;

//input이 길 경우 파일로 넣어준다.
FILE* in = fopen("input.txt", "r");

int n, m;
int map[501][501];
bool visited[501][501];
// 디버깅용 pair 배열
// pair<int, int> path[4];
// DFS를 위한 방향 정보
int dx[4]{ 0, 0, -1, 1 };
int dy[4]{ -1, 1, 0, 0 };
int max;

//재귀함수를 통한 DFS 구현
void tetro(int x, int y, int idx, int ret) {
	// 4가지를 돌면 max 값 비교
	if (idx == 4)
	{
		if (max < ret)
			max = ret;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int next_x = x + dx[i]; int next_y = y + dy[i];
        // 해당 셀이 방문하지도 않고, 범위 내에 있다면
		if (!visited[next_x][next_y] && next_x >= 0 && next_x < n && next_y >= 0 && next_y < m) {
			// 해당 셀에 방문했다고 표시
			visited[next_x][next_y] = true;
            // 디버깅용 경로 탐색
			// path[idx] = make_pair(x, y);
            // 다음 셀로 진행
			tetro(next_x, next_y, idx + 1, ret + map[x][y]);
            // 반드시 next_x, next_y에 check 한 것을 없애줘야 함.
			visited[next_x][next_y] = false;
		}
	}
}

//DFS에 해당하지 않는 것은 따로 구현해줌.
void non_dfs(int x, int y){
	//ㅗ
	int ret;
	if (x >= 1 && y < m-2)
	{
		ret = map[x][y] + map[x][y+1] + map[x][y + 2] + map[x - 1][y + 1];
		if (ret > max)
			max = ret;
	}
	//ㅏ
	if (x < n - 2 && y < m - 1)
	{
		ret = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y + 1];
		if (ret > max)
			max = ret;
	}
	//ㅜ
	if (x < n - 1 && y < m - 2)
	{
		ret = map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x + 1][y + 1];
		if (ret > max)
			max = ret;
	}
	//ㅓ
	if (x < n - 2 && y >= 1)
	{
		ret = map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y - 1];
		if (ret > max)
			max = ret;
	}
}

int main() {
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			fscanf(in, "%d", &map[i][j]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			visited[i][j] = true;
			tetro(i, j, 0, 0);
			visited[i][j] = false;
		}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			non_dfs(i, j);
	printf("%d", max);
}