글 읽기 - 저의 하드코딩에 두통이.....

qkqkaqk93 6년 전 0

하... 풀긴 하였으나, 저의 하드코딩에 마음이 아픕니다...

너무 보기 안좋지 않나요..ㅠㅠㅠㅠ

개선 방법 없을까요 ㅠㅠㅠ

#include <iostream>

#include <vector>
#include <stack>

using namespace std;
int main()
{
	int n, m;
	int max_Area = 0;
	int area_1 = 0;
	cin >> n >> m;
	vector<vector<int> > vec(n);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int a;
			cin >> a;
			vec[i].push_back(a);
			if (a == 1)
			{
				area_1++;
			}
		}
	}

	area_1 = area_1 + 3;
	
	for (int w1_y=0; w1_y < n; w1_y++)
	{
		for (int w1_x=0;w1_x < m; w1_x++)
		{
			if (vec[w1_y][w1_x] == 0)
			{
				vec[w1_y][w1_x] = 4;

				for (int w2_y= w1_y; w2_y < n; w2_y++)
				{
					for (int w2_x = 0; w2_x < m; w2_x++)
					{
						if (vec[w2_y][w2_x] == 0)
						{
							vec[w2_y][w2_x] = 4;

							for (int w3_y= w2_y; w3_y < n; w3_y++)
							{
								for (int w3_x = 0; w3_x < m; w3_x++)
								{
									if (vec[w3_y][w3_x] == 0)
									{
										vec[w3_y][w3_x] = 4;

										stack<pair<int, int> > stk;

										for (int i = 0; i < n; i++)
										{
											for (int j = 0; j < m; j++)
											{
												if (vec[i][j] == 2)
												{
													stk.push(make_pair(i, j));
												}
											}
										}

										int cnt = 0;

										while (!stk.empty())
										{
											int y = stk.top().first;
											int x = stk.top().second;
											stk.pop();

											cnt += 1;

											int dest_y = y - 1;
											int dest_x = x;
											if (dest_y >= 0 && dest_y < n && dest_x >= 0 && dest_x < m
												&& vec[dest_y][dest_x] == 0)
											{
												stk.push(make_pair(dest_y, dest_x));
												vec[dest_y][dest_x] = 3;
											}
											dest_y = y + 1;
											dest_x = x;
											if (dest_y >= 0 && dest_y < n && dest_x >= 0 && dest_x < m
												&& vec[dest_y][dest_x] == 0)
											{
												stk.push(make_pair(dest_y, dest_x));
												vec[dest_y][dest_x] = 3;
											}
											dest_y = y;
											dest_x = x - 1;
											if (dest_y >= 0 && dest_y < n && dest_x >= 0 && dest_x < m
												&& vec[dest_y][dest_x] == 0)
											{
												stk.push(make_pair(dest_y, dest_x));
												vec[dest_y][dest_x] = 3;
											}
											dest_y = y;
											dest_x = x + 1;
											if (dest_y >= 0 && dest_y < n && dest_x >= 0 && dest_x < m
												&& vec[dest_y][dest_x] == 0)
											{
												stk.push(make_pair(dest_y, dest_x));
												vec[dest_y][dest_x] = 3;
											}
										}

										for (int i = 0; i < n; i++)
										{
											for (int j = 0; j < m; j++)
											{
												if (vec[i][j] == 3)
												{
													vec[i][j] = 0;
												}
											}
										}

										if (max_Area < n*m - (area_1 + cnt))
											max_Area = n*m - (area_1 + cnt);
										cnt = 0;

										vec[w3_y][w3_x] = 0;
									}
								}
							}
							vec[w2_y][w2_x] = 0;
						}
					}
				}
				vec[w1_y][w1_x] = 0;
			}
		}
	}
		

	cout << max_Area << endl;

	return 0;
}

3587jjh 6년 전 0

함수를 이용해서 메인함수가 하는 일을 세분화하는게 좋을것같아요

gilsu91 6년 전 0

고수는 아니지만 댓글 달아봅니다.

제 스타일로 한번 정리해봤습니다.

일단

for 2개로 하나씩 선택하는걸 3번 반복하면서,

DFS수행하고 나서,

공간 구하고, max 여부비교

로 짜셨네요.

1. func1, func2, func3로 쪼겠습니다. 각각 for문 2개로 만들어졌습니다.

func3에서 첫번째 선택, func2에서 두번째 선택, func1에서 세번째꺼 선택하고

Dfs 실행합니다.

이름 정하는게 제일 어려워요ㅋㅋㅋㅋㅋ

2. 방향마다 코드 쓰셨길래,

typedef struct position { int y, x; }p;

const p dir[] = { { 0,1 },{ 0,-1 },{ -1,0 },{ 1,0 } };

요거 만들어서 정리했습니다.

3. 이미 선택한거 또 선택하길래 픽했던거 이전꺼는 다시 선택 안하게 바꿨습니다.

말로하기 어렵네요.

func2, func1에 적용했는데, func3랑 비교하시면 이해 가실 겁니다.

func3에서는 가장 먼저 하나 선택하니까 이전 꺼는 없잖아요.

func2, func1은 이전에 픽한게 있으니까 중복 안하게 했어요.

52ms걸렸는데 44ms로 줄었습니다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n, m, max_Area = 0, area = 3;
vector<vector<int>> vv;
typedef struct position { int y, x; }p;
const p dir[] = { { 0,1 },{ 0,-1 },{ -1,0 },{ 1,0 } };
void DFS_and_chk_ANS() 
{
	stack<p> stk;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (vv[i][j] == 2)
				stk.push({ i,j });

	int cnt = 0;
	while (!stk.empty())
	{
		p now = stk.top(); stk.pop();
		++cnt;
		for (auto &each : dir) 
		{
			p nxt = { now.y + each.y, now.x + each.x };
			if (nxt.y < 0 || nxt.y >= n) continue;
			if (nxt.x < 0 || nxt.x >= m) continue;
			if (vv[nxt.y][nxt.x] == 0)
				stk.push(nxt), vv[nxt.y][nxt.x] = 3;
		}
	}

	for (auto &v : vv)
		for (auto &each : v)
			if (each == 3) each = 0;

	if (max_Area < n*m - (area + cnt))
		max_Area = n*m - (area + cnt);
}
void func1(const int &yy, const int &xx) 
{
	int x;
	for (int y = yy; y < n; ++y) 
	{
		if (y == yy) x = xx + 1;
		else x = 0;
		for (; x < m; ++x)
			if (vv[y][x] == 0) 
			{
				vv[y][x] = 4;
				DFS_and_chk_ANS();
				vv[y][x] = 0;
			}
	}
}
void func2(const int &yyy, const int &xxx) 
{
	int xx;
	for (int yy = yyy; yy < n; ++yy) 
	{
		if (yy == yyy) xx = xxx + 1;
		else xx = 0;
		for (; xx < m; ++xx)
			if (vv[yy][xx] == 0) 
			{
				vv[yy][xx] = 4;
				func1(yy, xx);
				vv[yy][xx] = 0;
			}
	}
}
void func3() 
{
	for (int yyy = 0; yyy < n; ++yyy)
		for (int xxx = 0; xxx < m; ++xxx)
			if (vv[yyy][xxx] == 0) 
			{
				vv[yyy][xxx] = 4;
				func2(yyy, xxx);
				vv[yyy][xxx] = 0;
			}
}
int main() 
{
	cin >> n >> m;
	vv.resize(n, vector<int>(m));

	for (auto &v : vv)
		for (auto &each : v) 
		{
			cin >> each;
			if (each == 1)
				area++;
		}
	func3();
	cout << max_Area << endl;
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

저의 하드코딩에 두통이.....

qkqkaqk93 6년 전 0

3587jjh 6년 전 0

gilsu91 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말