[프로그래머스] 석유 시추 (PCCP 기출문제) (C++)

Key

DFS를 활용한 간단한 문제 같지만, 시간복잡도를 고려해서 잘 풀어야한다.

 

Idea

가장 먼저 생각난 아이디어는 '열부터 탐색하면서 열이 바뀔 때마다 DFS로 석유 덩어리 구하기' 이다.

하지만 이 방법을 쓰게되면 열이 바뀔 때마다 방문 배열을 초기화해야하고, 시간복잡도가 n*m*n*m라서 시간초과가 발생한다. 하지만 난 시간초과가 된다는 걸 알면서도 그냥 이 방법으로도 코드를 짜보고 싶었다. 이유는 없다..

 

아래는 정확성은 통과하지만 효율성은 모두 통과하지 못하는 코드이다.

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

using namespace std;

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool visited[500][500]={false,};
int cnt=0;

bool isRange(int x, int y, int n, int m){
    return x>=0 && x<n && y>=0 && y<m;
} 

void init(int n, int m){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            visited[i][j]=false;
        }
    }
}

int DFS(int x, int y, vector<vector<int>>& land, int n, int m){
    cnt++;
    visited[x][y]=true;
    
    for(int i=0; i<4; i++){
        int nextX=x+dx[i];
        int nextY=y+dy[i];
        
        // 범위 안이고 석유이고 방문하지 않았다면
        if(isRange(nextX, nextY, n, m) && land[nextX][nextY]==1 &&!visited[nextX][nextY]){
            DFS(nextX, nextY, land, n, m);
        }
    }
    return cnt;
}

int solution(vector<vector<int>> land) {
    
    int answer = 0;
    int res=0;
    int n=land.size();
    int m=land[0].size();
    
    // 열 - 행 순으로 탐색
    for(int j=0; j<m; j++){
        
        // 방문배열, 결과값 초기화
        init(n, m);
        cnt=0;
        
        for(int i=0; i<n; i++){
            // 석유가 있고 아직 방문 안했다면
            if(land[i][j]==1 && !visited[i][j]){
                res= DFS(i, j, land, n, m);
            }
        }
        answer=max(answer, res);
    }
    
    return answer;
}

 

시간복잡도 문제를 해결하려면 다음과 같이 접근해야한다.

석유 크기는 한번만 구해두면 된다. 근데 이걸 어떤 방식으로 구현하고 값을 저장할 것인가?

 

나는 각 석유 덩어리에 번호를 붙여주고 이 번호를 이용해서 저장된 석유 덩어리 크기에 접근할 수 있게 만들었다.

방법은 매우 쉽다. 말로 하면 복잡하니 그림으로 설명을 해봤다. 나는 덩어리 번호를 0부터 시작했기 때문에 landIdx 배열을 -1로 초기화했다. 그러니까 시추할 때 만약 landIdx[x][y]가 -1이 아니고 아직 방문하지 않은 덩어리라면 landSize[덩어리번호]로 덩어리 크기를 더해주면 된다. 덩어리 크기를 저장할 landSize는 벡터를 이용해서 구현했다.

 

DFS + 라벨링 방식은 백준의 다리만들기에서도 쓰인다. 이 방법에 익숙하지 않다면 다리만들기도 풀어보는 것을 추천한다.

 

 

Code

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

using namespace std;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool visited[500][500] = { false, };
int landIdx[500][500];
vector<int>landSize;
int cnt = 0, idx = 0;

bool isRange(int x, int y, int n, int m) {
    return x >= 0 && x < n&& y >= 0 && y < m;
}

int DFS(int x, int y, vector<vector<int>>& land, int n, int m) {
    int cnt = 1;
    visited[x][y] = true;
    landIdx[x][y] = idx;

    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        // 범위 안이고 석유이고 방문하지 않았다면
        if (isRange(nextX, nextY, n, m) && land[nextX][nextY] == 1 && !visited[nextX][nextY]) {
            cnt += DFS(nextX, nextY, land, n, m);
        }
    }
    return cnt;
}

int solution(vector<vector<int>> land) {

    int answer = 0;
    int n = land.size();
    int m = land[0].size();

    fill(&landIdx[0][0], &landIdx[0][0] + 500 * 500, -1);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 석유가 있고 아직 방문 안했다면
            if (land[i][j] == 1 && !visited[i][j]) {
                int res = DFS(i, j, land, n, m);
                landSize.push_back(res);
                idx++;
            }
        }

    }

    // 시추하기
    // 열 - 행 순으로 탐색
    for (int j = 0; j < m; j++) {
        int sum = 0;
        vector<bool>landVisited(landSize.size(), false);
        for (int i = 0; i < n; i++) {
            int value = landIdx[i][j];
            if (value != -1 && !landVisited[value]) {
                landVisited[value] = true;
                sum += landSize[value];
            }
        }
        answer = max(answer, sum);
    }

    return answer;
}