[Programmers] PCCP 기출문제 2

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

 

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

 

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

 

 

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500

정확성 테스트 케이스 제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

 

내가 도입한 개념은 다음과 같다. 

N*N 탐색을 진행해서 석유를 처음 만나면 BFS 를 진행한다.

그렇게 BFS를 통해서 인접한 석유를 탐색하는 한 과정을 마을을 구성하는 과정이라고 하자. 

 

- 500 X 500 크기의 배열에서 각 칸이 속하는 마을을 저장한다. -> numberOfVillage[510][510]

- 각 마을 별로 그 마을의 크기를 저장한다. -> villageCount[125010] 

 

- 위 방식을 수행하면서, 이미 numberOfVillage가 저장된 칸을 방문할 경우, BFS를 따로 수행하지 않고 VillageCount에서 마을의 크기를 구해서 더한다 .

- 이 방식을 각 열에 대해, 모든 행을 수행하면서 탐색하되, 이미 방문한 마을인지 아닌지 확인하기 위해 이중 for문 중 내부 for문 이전에 checkVisit 배열을 두어 확인한다. (또는 Set 사용)

 

 

<주의점>

- solution에 주어진 land 벡터를 인자로 줄 때는, 레퍼런스로 주어서 불필요한 복사가 일어나지 않도록 한다.

- 마을의 최대 개수는 각 칸의 개수 / 2 와 같으므로, 500 * 500 / 2이다. 

 

 

 

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


using namespace std;
int N, M;
int numberOfVillage[501][510] = {0,};
int villageCount[125010] = {0,}; //마을 번호에 대한 개수
int curVillage = 1;
long long answer = 1;

bool canGo(int r, int c){
    return 0 <= r && r < N && 0 <= c && c < M;
}

void bfs(int r, int c, int v, vector<vector<int>>& land) {
    int count = 1;
    queue<pair<int, int> > Q;
    Q.push(make_pair(r, c));
    numberOfVillage[r][c] = v;
   
    int dir[4][2] = {{0,1}, {0,-1}, {1,0}, {-1, 0}};
    while (!Q.empty()) {
        int curR = Q.front().first;
        int curC = Q.front().second;
        Q.pop();
        for(int i = 0; i < 4; i++) {
            int nextR = curR + dir[i][0];
            int nextC = curC + dir[i][1];
            if (canGo(nextR, nextC) == false)
                continue;
            if (numberOfVillage[nextR][nextC] == 0 && land[nextR][nextC] == 1) {
                numberOfVillage[nextR][nextC] = v;
                count++;
                Q.push(make_pair(nextR, nextC));
            }
        }
    }
    villageCount[v] = count;
    // return count;
    
 
}

long long max(long long a, long long b){
    return a > b ? a : b;
}

long long solution(vector<vector<int>> land) {
    N = land.size();
    M = land[0].size();

    curVillage = 1;
    for (int j = 0; j < M; j++) {
        long long count = 0;
        // set<int> checkVisited;
        bool checkVisited[125010] = {0,};
        // long long c = 1 << ()
        
        // cout << "j : " << j << "\n";
        for (int i = 0; i < N; i++) {
            int village = numberOfVillage[i][j];
            if (village == 0 && land[i][j] == 1) {
                bfs(i, j, curVillage, land); 
                count += villageCount[curVillage]; 
                checkVisited[curVillage++] = true;
                // checkVisited.insert(curVillage++);
            }
            else if(village != 0 && land[i][j] == 1){
                // if(checkVisited.find(village) == checkVisited.end()){
                if(checkVisited[village] == false) {
                    count += villageCount[village];
                    checkVisited[village] = true;
                    // checkVisited.insert(village);
                }
            }
            // cout << "i " << i << "count " << count << "\n";
        }
        answer = max(answer, count);
    }
    
    return answer;
}