[프로그래머스] Level 2 : 석유 시추

https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

 

해당 문제는 일반적인 BFS로 풀면 효율성 검사에서 시간초과가 난다.

 

한 번 시추한 석유 뭉치는 다른 x축에서 중복으로 검사할 필요가 없다.

1번에서 석유 뭉치를 시추하여 8의 결과를 얻었으면, 2번과 3번에서는 해당 석유 뭉치를 발견하면 바로 8임을 알고 넘어갈 수 있다.

이렇게 하면, 일단 시간 초과는 해결할 수 있다.

 

다음으로, y축으로 내려가며 같은 석유 뭉치를 발견한 경우이다.

각 석유 뭉치마다 석유 번호를 매겨 이미 검사한 석유 뭉치인지를 방문체크해줘야 한다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int dy[]{ -1, 0, 1, 0 };
int dx[]{ 0, 1, 0, -1 };

void BFS(const pair<int, int>& Start, vector<vector<pair<int, int>>>& Save, const vector<vector<int>>& land, const int& Cnt)
{
	vector<pair<int, int>> Count{ Start }; // 같은 석유 땅의 수와 좌표
	queue<pair<int, int>> q;
	q.push({ Start.first, Start.second });
	Save[Start.first][Start.second].first = Cnt; // 석유 땅에 현재 석유 번호 배정

	while (!q.empty())
	{
		int y = q.front().first, x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= land.size() || nx >= land[0].size() || Save[ny][nx].first == Cnt || !land[ny][nx]) continue;

			Save[ny][nx].first = Cnt; // 연결된 석유 땅에도 현재 석유 번호 배정
			Count.push_back({ ny, nx });
			q.push({ ny, nx });
		}
	}

	// 최종적으로 연결된 모든 석유 땅에 같은 석유 번호와 같은 석유 양을 지정
	for (const auto& i : Count)
		Save[i.first][i.second].second = Count.size();
}

int solution(vector<vector<int>> land) {
	int answer = 0;

	// 땅 좌표{y, x}의 first = 석유 번호, second = 해당 석유 번호의 석유량
	vector<vector<pair<int, int>>> Save(land.size(), vector<pair<int, int>>(land[0].size(), { 0, 0 }));

	// Cnt = 석유 번호
	for (int y = 0, Cnt = 1; y < land.size(); ++y)
	{
		for (int x = 0; x < land[0].size(); ++x)
		{
			if (!land[y][x] || Save[y][x].first != 0) continue;
			BFS({ y, x }, Save, land, Cnt);
			Cnt++;
		}
	}

	for (int x = 0; x < land[0].size(); ++x)
	{
		// 현재 시추한 석유 번호
		vector<int> CheckCnt;
		int Num = 0;

		for (int y = 0; y < land.size(); ++y)
		{
			// 해당 좌표가 벽이면 스킵
			if (!land[y][x]) continue;

			// 현재 좌표의 석유 번호가 이미 시추한 석유 번호인경우 스킵
			vector<int>::iterator it = find(CheckCnt.begin(), CheckCnt.end(), Save[y][x].first);
			if (it != CheckCnt.end()) continue;

			// 시추한 석유 번호를 저장
			CheckCnt.push_back(Save[y][x].first);
			Num += Save[y][x].second;
		}
		answer = max(answer, Num);
	}
	return answer;
}