[프로그래머스 Level 2] 석유 시추(C++)

코딩테스트 연습 - [PCCP 기출문제] 2번 / 석유 시추 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

먼저 bfs 탐색으로 연결되어있는 석유 덩어리를 번호 메긴다. 이 때 리턴 값으로는 bfs 탐색 횟수로, 해당 석유 덩어리의 크기를 리턴해준다. 이를 map에 map[석유덩어리 번호] = 석유 덩어리 크기와 같이 저장해주고, 이후 중복되는 석유 덩어리 번호를 방지하기 위해 set 자료구조를 사용하여 각 열마다 석유 덩어리의 번호를 저장해준다.

#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;

int num = 1;
vector<vector<int>> v;
int moveY[4] = { 0,0,1,-1 };
int moveX[4] = { 1,-1,0,0 };

int bfs(int i, int j) {
	queue<pair<int, int>> q;
	q.emplace(i, j);
	v[i][j] = num;
	int total = 0;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		total++;
		for (int m = 0; m < 4; m++) {
			int nodeY = y + moveY[m];
			int nodeX = x + moveX[m];
			if (nodeY >= 0 && nodeY < v.size() && nodeX >= 0 && nodeX < v[0].size() && v[nodeY][nodeX] == 1) {
				v[nodeY][nodeX] = num;
				q.emplace(nodeY, nodeX);
			}
		}
	}
	return total;
}

map<int, int> m;
set<int> s[500];

int solution(vector<vector<int>> land) {
	int answer = 0;
	v = land;
	for (int i = 0; i < land.size(); i++) {
		for (int j = 0; j < land[0].size(); j++) {
			if (v[i][j] == 1) {
				num++;
				m[num]=bfs(i, j);
			}
		}
	}
	for (int j = 0; j< v[0].size(); j++) {
		for (int i = 0; i < v.size(); i++) {
			if (v[i][j] != 0) {
				s[j].insert(v[i][j]);
			}
		}
	}
	int maxNum = 0;
	for (int j = 0; j < v[0].size(); j++) {
		int total = 0;
		for (auto num : s[j]) {
			total += m[num];
		}
		if (maxNum < total)
			maxNum = total;
	}
	answer = maxNum;
	return answer;
}