[DFS] 14500 테트로미노 C++

Seunghyeon·2022년 12월 19일

DFS 구현

백준 문제 푼다.

목록 보기

2/21

문제를 풀면서 아무 생각없이 쭉 구현했을 때

'ㅗ, ㅏ, ㅜ, ㅓ' 모양을 제외하고는 전부 잘 동작한다.

우선 'ㅗ, ㅏ, ㅜ, ㅓ'를 제외한 구현

첫번째 코드

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

int n, m;

int g[501][501];
int visited[501][501] = { 0, };
// ㄷㅅㄴㅂ
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int result;

int MAX = 0;

int move(int dir, int total , int x, int y)
{
	if (dir == 0)
	{
		if (y + 1 < m && !visited[x][y + 1])
		{
			return g[x][y + 1] + total;
		}
	}
	else if (dir == 1)
	{
		if (y - 1 >= 0 && !visited[x][y - 1])
		{
			return g[x][y - 1] + total;
		}
	}
	else if (dir == 2 )
	{
		if (x + 1 < n && !visited[x + 1][y])
		{
			return g[x + 1][y] + total;
		}
	}
	else if (dir == 3 )
	{
		if (x - 1 >= 0 && !visited[x - 1][y])
		{
			return g[x - 1][y] + total;
		}
	}
}

void dfs(int cnt, int total, int x, int y)
{
	if (cnt == 4)
	{
		if (MAX < total)
			MAX = total;
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		if (x + dx[i] >= 0 &&
			x + dx[i] < n &&
			y + dy[i] >= 0 &&
			y + dy[i] < m &&
			!visited[x + dx[i]][y + dy[i]])
		{
			result = move(i, total, x, y);
			visited[x + dx[i]][y + dy[i]] = 1;
			dfs(cnt + 1, result, x + dx[i], y + dy[i]);
			visited[x + dx[i]][y + dy[i]] = 0;
		}
	}
}

int main()
{
	cin >> n >> m;

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

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

	cout << MAX;

	return 0;
}

이 코드를 작성하고 나서
'ㅗ,ㅏ,ㅓ,ㅜ' 얘내들을 어떻게 구현을 해야하나 생각을 했다.

그러다가 갑자기 코드가 너무 번잡하다는 생각이 들었는데

저 move 함수의 결과를 result에 넣어서 dfs를 다시 돌리는 부분이었다.

"저 부분은 result에 따로 넣지 않고 바로 함수로 넣으면 되는 부분이네?"

이렇게 하나하나 생각하다보니 move 함수 자체가 필요가 없었다...

인덱스로 값을 조정하고 그 결과를 move 함수에서 더해오기만 하기 때문이다.

그래서 이렇게 변경했다.

코드 수정 후

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
int n, m;
int g[501][501];
int visited[501][501] = { 0, };
// ㄷㅅㄴㅂ
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int MAX = 0;
void dfs(int cnt, int total, int x, int y)
{
	if (cnt == 4)
	{
		if (MAX < total)
			MAX = total;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		if (x + dx[i] >= 0 &&
			x + dx[i] < n &&
			y + dy[i] >= 0 &&
			y + dy[i] < m &&
			!visited[x + dx[i]][y + dy[i]])
		{
			visited[x + dx[i]][y + dy[i]] = 1;
			dfs(cnt + 1, total + g[x + dx[i]][y + dy[i]], x + dx[i], y + dy[i]);
			visited[x + dx[i]][y + dy[i]] = 0;
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> g[i][j];
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			memset(visited, 0, sizeof(visited));
			visited[i][j] = 1;
			dfs(1,g[i][j],i,j);
		}
	}
	cout << MAX;
	return 0;
}

아직 완성된 코드는 아니지만, 줄이고 보니
이 문제를 푸는동안 move 함수를 만드는데 든 시간이 아까웠다.

그리고 'ㅗ, ㅏ, ㅓ, ㅜ' 는 따로 구현해주었다.

최종 코드

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

int n, m;

int g[501][501];
int visited[501][501] = { 0, };
// ㄷㅅㄴㅂ
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int MAX = 0;

void dfs(int cnt, int total, int x, int y)
{
	if (cnt == 4)
	{
		if (MAX < total)
			MAX = total;
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		if (x + dx[i] >= 0 &&
			x + dx[i] < n &&
			y + dy[i] >= 0 &&
			y + dy[i] < m &&
			!visited[x + dx[i]][y + dy[i]])
		{
			visited[x + dx[i]][y + dy[i]] = 1;
			dfs(cnt + 1, total + g[x + dx[i]][y + dy[i]], x + dx[i], y + dy[i]);
			visited[x + dx[i]][y + dy[i]] = 0;
		}
	}

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

int main()
{
	cin >> n >> m;

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

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//memset(visited, 0, sizeof(visited));
			visited[i][j] = 1;
			dfs(1,g[i][j],i,j);
			visited[i][j] = 0;

		}
	}

	cout << MAX;

	return 0;
}