비전공자의 개발 버퍼

아이디어.

1.기본적으로 탐색은 dfs를 사용한다.
2.각 열에 시추관이 지날 때 마다 앞서 이미 조사한 석유블럭을 다시 조사하는 것을 막기 위해, 이미 조사한 블럭이라면 탐색하지 않고 Cash에 저장된 블럭의 수를 리턴하고 끝낸다.
3.Cash 이중배열 벡터를 만들고,  석유블럭 덩어리에 번호를 붙여 Size에 해당 덩어리의 크기를 저장한다.

코드 Ver.1

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

vector<vector<int>> Cash(501,vector<int>(501, -1));
vector<int> Size(501, 0);
int sizeCount = 0;

int Greater(int a, int b)
{
	if (a >= b)
	{
		return a;
	}
	else if (b >= a)
	{
		return b;
	}
}

void Dfs(vector<vector<int>> land, int row, int column, int& oil, int size)
{
	int dy[] = { 0, 1, 0 , -1 };
	int dx[] = { 1, 0, -1 , 0 };

	for (int i = 0; i < 4; i++)
	{
		int nextY = row + dy[i];
		int nextX = column + dx[i];

		if (nextY < 0 || nextX < 0 || nextY >= land.size() || nextX >= land[0].size() || Cash[nextY][nextX] != -1)
			continue;

		if (land[nextY][nextX] == 1 && Cash[nextY][nextX] == -1)
		{
			oil++;
			Cash[nextY][nextX] = size;
			Dfs(land, nextY, nextX, oil, size);
		}
	}
}

int solution(vector<vector<int>> land)
{
	int row = land.size();
	int column = land[0].size();

	int result = 0;
	int oil = 0;
	int answer = 0;


	for (int i = 0; i < column; i++)
	{
		vector<bool> visited(250, false);
		vector<int> v;//디버깅용

 		for (int j = 0; j < row; j++)
		{
			if (land[j][i] == 1 && Cash[j][i] == -1)//탐색시작
			{
				visited[sizeCount] = true;

				oil++;
				Cash[j][i] = sizeCount;
				Dfs(land,j,i,oil, sizeCount);

				Size[sizeCount] = oil;
				sizeCount++;
				
			}
			else if (land[j][i] == 1 && Cash[j][i] != -1 && visited[Cash[j][i]] == false)
			{
				visited[Cash[j][i]] = true;
				oil = Size[Cash[j][i]];
			}

			result += oil;
			v.push_back(oil);//디버깅용
			oil = 0; 
		}

		answer = Greater(answer, result);
		result = 0;
	}

    return answer;
}

결과.

 마지막 테스트를 실패하고 모든 테스트 케이스에서 시간 초과가 걸려버렸다.

 마지막 테스트 실패는 그렇다 치더라도 모든 테스트에서 시간초과가 나올줄은 몰랐다. 접근은 괜찮았다고 생각 했는데....

 일단 박제 해놓고 다시 해 봐야겠다.