코딩테스트 -- [PCCP 기출문제] 2번 / 석유 시추 - (프로그래머스 / C++)

 

 

프로그래머스

 

 

 

문제요약!

---

 

위 그림처럼 석유가 묻혀있는 땅에 시추관을 세로로 심을때 가장 많이 시추할 수 있는 석유의 양을 찾는 문제였습니다!

 

땅의 세로 가로가 500으로 제한되어있어, 꼬아서 생각할 필요없이 석유의 양과 열을 탐색을 통해 구해, 풀어주었습니다.

 

 

---

 

 

그럼 코드 시작!

 

 

저는 먼저 탐색을 통해 석유의 양과 석유덩어리들이 포함하는 열을 찾아주기로 하였습니다.

 

이미 land벡터의 값들이 0과 1로 석유가 있는지 없는지로 입력을 받아주었기에

visit벡터에 복사해주고, 기본적인 정보를 저장해주며 시작해주었습니다. 

 

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

	int n = land.size();
	int m = land[0].size();
	visit = land; // 방문 ㅇㅇ 빌리기

	for (int i = 0; i < land.size(); i++) {
		for (int j = 0; j < land[0].size(); j++) {// 탐색 시작 위치 지정
			if (visit[i][j] == 1) { // 석유발견! 시작
				Amount_A = 0;
				number_A.clear();

				dfs(i, j);

				sort(number_A.begin(), number_A.end());
				number_A.erase(unique(number_A.begin(), number_A.end()), number_A.end());
				
				for(int k=0;k< number_A.size();k++){ // 각 번호
					number_T[number_A[k]] += Amount_A;
				}


			}

		}
	}

 

Amount_A, number_A 에는 현재 텀색할 석유 덩어리의 양과 열의 번호들을 저장해 주었고

열번호의 경우 erase,unique 함수를 통해 중복을 제거한 후

 

각 열에 시추관을 연결할시 최대 석유량을 number_A에 저장해 주었습니다.

 

 

 

 

 

탐색의 경우 기본적인 dfs탐색으로 진행해 주었습니다.

석유의 양과 열번호를 저장, visit[][]=0 처리하며, 탐색을 진행해 주었습니다. 

int Amount_A;
vector<int> number_A;

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


void dfs(int i,int j) { // 석유 탐색   x,y ,양, 열 번호
	
	if (i<0 || i>=visit.size() || j<0 || j>=visit[0].size()) {
		return;
	}
	else {
		if (visit[i][j] == 0) {
			return;
		}
		else { // 기름
			visit[i][j] = 0;
			number_A.push_back(j);
			Amount_A += 1;

			for (int k = 0; k < 4; k++) {
				dfs(i+dx[k], j + dy[k]);

			}
		}
	}
}

 

 

 

 

그리고 마지막으로 number_T에 열번호별 최대 석유량을 비교해주어 최댓값을 구해주면 끝!

 

 

for (int i = 0; i < land[0].size(); i++) {


		if (number_T[i] > answer) {
			answer = number_T[i];
		}
	}

 

 

 

 

 

그림만 보고 겁먹을 수 있는 문제였지만,

석유덩어리 별로 탐색한 결과를 저장해주기만 하면 쉽게 풀리는 문제였습니다!

 

 

 

 

 

 

 

 

 

ALL

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// 석유 덩어리들의 크기와 열번호를 저장하고 500개 다 넣어서 최대 석유 구하기
// 각 라인에 연결된 

vector<int> amount;			// 각 석유 덩어리들의 석유량
vector<vector<int>> number; // 각 석유 덩어리들의 열번호리스트



int number_T[501]={0,};// 각 열에 포함된 석유 번호들


vector<vector<int>> visit;


int Amount_A;
vector<int> number_A;

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


void dfs(int i,int j) { // 석유 탐색   x,y ,양, 열 번호
	
	if (i<0 || i>=visit.size() || j<0 || j>=visit[0].size()) {
		return;
	}
	else {
		if (visit[i][j] == 0) {
			return;
		}
		else { // 기름
			visit[i][j] = 0;
			number_A.push_back(j);
			Amount_A += 1;

			for (int k = 0; k < 4; k++) {
				dfs(i+dx[k], j + dy[k]);

			}
		}
	}
}


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

	int n = land.size();
	int m = land[0].size();
	visit = land; // 방문 ㅇㅇ 빌리기

	for (int i = 0; i < land.size(); i++) {
		for (int j = 0; j < land[0].size(); j++) {// 탐색 시작 위치 지정
			if (visit[i][j] == 1) { // 석유발견! 시작
				Amount_A = 0;
				number_A.clear();

				dfs(i, j);

				sort(number_A.begin(), number_A.end());
				number_A.erase(unique(number_A.begin(), number_A.end()), number_A.end());
				
				for(int k=0;k< number_A.size();k++){ // 각 번호
					number_T[number_A[k]] += Amount_A;
				}


			}

		}
	}

	for (int i = 0; i < land[0].size(); i++) {


		if (number_T[i] > answer) {
			answer = number_T[i];
		}
	}

	return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!