https://school.programmers.co.kr/learn/courses/30/lessons/250136
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이 문제는 간단한 문제인줄 알고 건드렸다가 2시간을 날릴 정도로 고생한 문제이다
일단 이 문제의경우 딱 봤을 때 BFS를 사용하는거는 확실 해 보이지만 매번 시추할 때 마다 BFS를 돌리면 효율성 검사에서 점수가 떨어지게 된다 이에 이문제는 BFS를 이용해서 뽑아낸 데이터를 어떤 자료 구조에 넣어 사용하는 지가 매우 중요한 문제이다
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int directionX[4] = { 1, 0, -1, 0 };
int directionY[4] = { 0, 1, 0, -1 };
int isVisited[501][501] = { 0, };
map<int, int> sizeOfOil;
int sizeOfLandX;
int sizeOfLandY;
int areaNum = 1;
vector<vector<int>> oilMap;
void BFS(int startX, int startY ) {
int tmp = 0;
queue<pair<int, int>> q;
q.push({ startX, startY });
oilMap[startX][startY] = areaNum;
isVisited[startX][startY] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
tmp++;
q.pop();
for (int i = 0; i < 4; i++) {
int nextX = x + directionX[i];
int nextY = y + directionY[i];
if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
oilMap[nextX][nextY] = areaNum;
isVisited[nextX][nextY] = 1;
q.push({ nextX,nextY });
}
}
}
sizeOfOil[areaNum] = tmp;
areaNum++;
}
int solution(vector<vector<int>> land) {
int answer = 0;
oilMap = land;
sizeOfLandX = land.size(); //열의 길이
sizeOfLandY = land[0].size(); //행의 길이
for (int i = 0; i < sizeOfLandX; i++) {
for (int j = 0; j < sizeOfLandY; j++) {
if (isVisited[i][j] == false && land[i][j] == 1) {
BFS(i, j);
}
}
}
for (int j = 0; j < sizeOfLandY; j++) {
set<int> oilSet;
int sumOfOil=0;
for (int i = 0; i < sizeOfLandX; i++) {
oilSet.insert(oilMap[i][j]);
}
set<int>::iterator iter;
for (auto it : oilSet) {
sumOfOil += sizeOfOil[it];
}
answer = max(answer, sumOfOil);
}
return answer;
}일단 이 문제의 경우 내가 블로그에 기존에 올렸던 BFS보다 간단 하다 원래는 Direction을 일일히 내가 정해줬었는데 이를 배열에 넣어 간단하게 보이게 했다. 코드 가독성이 올라가니 확실히 디버깅 효율이 올라갔다
자 일단 이문제의 핵심로직은 BFS로 구해놓은 영역의 유전의 크기를 영역별로 들고 있어야 한다 이를 위해 위 코드에
void BFS(int startX, int startY ) {
int tmp = 0;
queue<pair<int, int>> q;
q.push({ startX, startY });
oilMap[startX][startY] = areaNum;
isVisited[startX][startY] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
tmp++;
q.pop();
for (int i = 0; i < 4; i++) {
int nextX = x + directionX[i];
int nextY = y + directionY[i];
if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
oilMap[nextX][nextY] = areaNum;
isVisited[nextX][nextY] = 1;
q.push({ nextX,nextY });
}
}
}
sizeOfOil[areaNum] = tmp;
areaNum++;
}BFS 부분에서sizeOfOil에 저장해 주었다 여기서 sizeOfOil은 맵 자료형이다 맵자료형은 map<int,int>이렇게 사용했을 때 맨앞에 오는 값은 Key로서 두번쨰 오는 값은 value로 써 작용합니다.
즉 map<key, value> 의 형태로 각각의 해당하는 자료형을 넣어주면 됩니다 .
이 문제에서는 Map의 저장해놓은 데이터를 순환하여 찾아와야 하기 때문에
for (auto iter = m.begin() ; iter != m.end(); iter++)
{
cout << iter->first << " " << iter->second << endl;
}
cout << endl;의 형태와
for (auto iter : m) {
cout << iter.first << " " << iter.second << endl;
}의 형태의 두가지 형태로 map을 순환 할 수 있습니다.
이에 필자는 두번째 형태로 사용하였습니다.
이렇게 Map형태로 저장해놓은 데이터에서 우리는 land 배열에 새로줄에서 만나는 areaNum들을 set에 넣어줍니다.
Set은 마찬가지로 중복되는 자료를 넣으면 넣지 않기 때문에 areaNum을 최대 1번씩만 넣을 수 있습니다
이에 set.insert를 이용해서 각 세로줄에 있는 유전의 areaNum을 넣습니다.
그후 이를 순회하면서 areaNum을 통해 세로줄에 있는 해당 유전에 크기를 더하여 최대값을 출력합니다
