[PCCP 기출문제] 2번 / 석유 시추

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

 

간단하게 풀 수 있는 BFS 문제였습니다.

시추관을 수직으로 꽂기 때문에 각 x 좌표마다 석유를 얼마나 뽑을 수 있는지 구하면 되는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. land 이차원 벡터를 순회하며 BFS 알고리즘을 통해 뽑을 수 있는 석유의 양을 구합니다.

1.1 핵심은 각 x 좌표마다 석유를 얼마나 뽑을 수 있는지를 구하는 것이기 때문에 1번에서 구한 석유의 양을 maxOil[석유가 분포되어 있는 각 x 좌표]에 더해줍니다.

2. 1번에서 구한 maxOil 배열 내 최대 값을 반환해줍니다.

 

	#include <string>
	#include <vector>
	#include <queue>
	#include <set>
	#include <algorithm>
	using namespace std;
	const int MAX = 500 + 5;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	bool visited[MAX][MAX];
	int maxOil[MAX];
	int solution(vector<vector<int>> land) {
	int N = land.size();
	int M = land[0].size();
	for (int y = 0; y < N; y++)
	{
	for (int x = 0; x < M; x++)
	{
	if (!land[y][x] || visited[y][x])
	{
	continue;
	}
	set<int> xSet;
	queue<pair<int, int>> q;
	q.push({y, x});
	visited[y][x] = true;
	int cnt = 0;
	while (!q.empty())
	{
	int curY = q.front().first;
	int curX = q.front().second;
	xSet.insert(curX);
	cnt++;
	q.pop();
	for (int k = 0; k < 4; k++)
	{
	int nextY = curY + moveDir[k].y;
	int nextX = curX + moveDir[k].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
	{
	continue;
	}
	if (visited[nextY][nextX] || !land[nextY][nextX])
	{
	continue;
	}
	visited[nextY][nextX] = true;
	q.push({nextY, nextX});
	}
	}
	for (int x : xSet)
	{
	maxOil[x] += cnt;
	}
	}
	}
	sort(maxOil, maxOil + MAX);
	return maxOil[MAX - 1];
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE 

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~