[프로그래머스] [PCCP 기출 문제] 2번 / 석유 시추 C++

1. 문제 설명

• 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

---

2. 풀이 과정 

• 문제 해결의 흐름 (bfs 이용)
  1. 석유 지도 (land)를 탐색하며 석유를 찾는다.
  2. 석유를 찾았다면 bfs를 통해 석유 덩어리의 크기를 파악하고 해당 석유 덩어리를 캘 수 있는 모든 column값을 집합(set)에 저장한다. (column값들의 중복을 제거하기 위해 집합에 저장함!)
  3. bfs 탐색이 끝났다면 column 위치 중 어느 위치에서 시추하는 것이 가장 많은 석유를 캘 수 있을지 찾자!
• 나의 코드

#include <string>
#include <vector>
#include <queue>
#include <set>

using namespace std;


struct Coordinate {
    int row; // 행
    int col; // 열
};

// 석유 덩어리 구조체
struct OilBlock {
    set<int> block; // 석유 덩어리의 열 위치
    int volume; // 석유 덩어리의 크기
};

vector<vector<int> > landMap;
int numRows, numCols; // 석유 지도의 행과 열의 개수
bool visited[501][501]; // 방문 여부를 저장하는 배열

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

OilBlock bfs(Coordinate start) {
    queue<Coordinate> q;
    q.push(start);
    set<int> oilPositions;

    int count = 1;  // 석유 개수
    oilPositions.insert(q.front().col); // 석유의 열 위치

    while (!q.empty()) {
        int currRow = q.front().row;
        int currCol = q.front().col;
        q.pop();

        for (int i = 0; i < 4; i++) { // 석유 주위 4방향을 탐색하며 다른 석유 찾기
            int newRow = currRow + dy[i];
            int newCol = currCol + dx[i];

            if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && !visited[newRow][newCol] && landMap[newRow][newCol] == 1) { // 범위값 만족하는지 확인하기
                count++;    // 석유 크기 + 1
                visited[newRow][newCol] = true;;
                Coordinate next = {newRow, newCol};
                q.push(next);
                oilPositions.insert(newCol);    // newCol 열에서 석유 발견!!
            }
        }
    }

    OilBlock result;
    result.block = oilPositions;
    result.volume = count;
    return result;
}

int solution(vector<vector<int> > land) {
    numRows = land.size();
    numCols = land[0].size();
    landMap = land;

    fill_n(&visited[0][0], numRows * numCols, false);

    vector<OilBlock> oilBlocks;
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            if (land[i][j] == 1 && !visited[i][j]) {
                Coordinate start = {i, j};
                visited[i][j] = true;
                oilBlocks.push_back(bfs(start));
            }
        }
    }

    int answer[501] = {0};  // 열 위치 정보들
    int maxNum = 0; // 캘 수 있는 가장 많은 석유량
    for (int i = 0; i < oilBlocks.size(); i++) {
        for (auto col : oilBlocks[i].block) {
            answer[col] += oilBlocks[i].volume;
            maxNum = max(answer[col], maxNum);
        }
    }

    return maxNum;
}

 

• 이 문제를 통해 얻어갈 수 있는 것들 
  • ⭐️ 행 : row, 열 : column이다. (은근 헷갈린다 ㅠㅠ.. 2차원 배열[행][열]도 꼭 기억하자. 또한 x : 열, y : 행)
  • ⭐️ 2차원 벡터에 대해서 vector.size();는 행, vector[0].size();는 열을 나타낸다. 
  • 집합(set)을 통해 중복된 값을 피할 수 있다. 
  • ⭐️ 다음 2가지 방법을 통해 집합 내를 순회할 수 있다. 

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;

    // 첫 번쨰 방법 (iterator란 컬렉션 요소의 주소 순회하는 포인터)
    for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++) {
        cout << *iter << endl;
    }

    // 두번째 방법
    for (auto x : s) {
        cout << x << endl;
    }

    return 0;
}

---

3. 후기

 set을 자주 사용하지 않았기에 고생했다. ㅠㅠ... 

 결과를 출력하는 과정에서 다음 블로그를 참고하였다. 

https://howudong.tistory.com/434

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