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

 

 

 

석유 시추 bfs 로  석유를 미리 번호를 지어두는 작업이 필요하다고 생각한다.

그리고 좌측부터 1자로 내리면서  제일큰걸 확인해보면 되는문제라 생각한다.

 

 

 

해당문제라면

 

1 [ 0,0], [ 0,1] [ 0,2] [ 0,3] [ 0,4]....  12

2 [2,0] [ 2,1] [ 2,2] 3

....

 

재귀로 bfs 탐색을하며 해당처럼 데이터를 모아준다

 

모아두었기때문에 한번 건들인 석유를 두번 캐지않을수있다.

 

 

 

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


static int const nextland[4][2]{ {0,1}, {1,0}, {-1,0}, {0,-1} };

//석유 룰 묶어주는 함수
void find_oil(vector<vector<int>>& land, int x, int y, int& oil_count, unordered_map<int, int>& oil_monny) {
	queue<tuple<int, int>> nextxy;
	nextxy.push(make_tuple(x, y));
	land[x][y] = oil_count;
	oil_monny[oil_count]++;
	while (nextxy.size() != 0)
	{


		tuple<int, int> nxy = nextxy.front();
		int xy[2]{ get<0>(nxy),get<1>(nxy) };
		nextxy.pop();


		int x, y = 0;
		for (auto arrow : nextland) {
			y = arrow[1] + xy[1];
			x = arrow[0] + xy[0];
			if (x >= 0 && x < land.size() && y >= 0 && y < land[0].size() && land[x][y] == 1) {
				land[x][y] = oil_count;
				oil_monny[oil_count]++;
				nextxy.push(make_tuple(x, y));
			}
		}
	}
	oil_count++;
}

int solution(vector<vector<int>> land) {
	int answer = 0;
	int oil_count = 2;
	unordered_map<int, int> oil_monny;

	for (int i = 0; i < land.size(); i++) {
		for (int j = 0; j < land[i].size(); j++) {
			if (land[i][j] == 1) {
            
            //석유를 한번에 모아주고 그 모은 석유의 벨류 탐색
				find_oil(land, i, j, oil_count, oil_monny);
			}
		}
	}


	for (int i = 0; i < land[0].size(); i++) {
		vector<bool>c(oil_count - 2);
		int b =0;
		for (int j = 0; j < land.size(); j++) {
        //아래로 내리면서 기름 있는땅 찾고 만약 탐색 안되었으면
			if (land[j][i] > 1 && (c[land[j][i] - 2] == false)) {
            //탐색완료 표시
				c[land[j][i] - 2] = true;
				// 현재 벨류 추가
                b += oil_monny[land[j][i]];
			}
		}
		if (answer < b) {
			answer = b;
		}
	}

	return answer;
}