[프로그래머스] Level 2. 석유 시추

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

프로그래머스

 

 

해결 방법

간단한 방법은 이렇다.

• 행렬  land 에 id = 2 부터 시작해서 덩어리에 번호를 매긴다. land[i][j] = 3 이면 3번덩어리라는 의미이다.
• dummy 라는 리스트를 생성한다 dummy[3] 은 3번 덩어리의 총 수 이다.  
• 위 작업을 완료 한 뒤, 열을 쭉 읽으면서 포함되는 번호를 찾는다. {2,3}이 나왔을 경우 dummy[2] + dummy[3] 이 추출된 석유 양이다.

덩어리값을 매기기 위해서는 행렬을 처음부터 돌면서 id를 수정하는 작업을 해주면된다.

land[i][j] 가  0이라면 석유가 없다는 의미 / 1이라면 석유가 있고, 아직 덩어리 번호를 부여받지 못했다는 의미 / 2 이상이라면 덩어리 번호를 이미 부여받았다는 의미이다.

1에 해당할때만 점검을 시작하면된다. 점검은 check() 함수에서 재귀로 이루어진다. 1을 만날때까지 상,하,좌,우를 재귀적으로 검사하고 유효한 곳에 덩어리id를 입력한다.

 

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

using namespace std;

void check(vector<vector<int>>& land, vector<int>& dummy,  int num, int i , int j){
	//범위를 벗어나거나, 값이 1이 아닌경우는 바로 종료
    if(i<0 || j<0 || i>=land.size() ||j>=land[0].size()||  land[i][j] != 1)return;
    
    if(dummy.size()<=num) dummy.push_back(0);
    
    //덩어리 id를 부여하고 개수 증가
    land[i][j] = num;
    dummy[num] +=1;
    
    check(land,dummy,num,i+1,j);
    check(land,dummy,num,i-1,j);
    check(land,dummy,num,i,j-1);
    check(land,dummy,num,i,j+1);
    
}

int solution(vector<vector<int>> land) {
    
    vector<int> dummy;
    
    //0과 1번 인덱스는 사용하지 않으므로 빈 값 추가
    dummy.push_back(0);
    dummy.push_back(1);
    
    
    for(int i=0 ;i<land.size(); i++){
        for(int j=0; j<land[0].size(); j++){
            if(land[i][j] != 1) continue;
            check(land,dummy, dummy.size(),i,j);
        }
    }
    
    
    int answer = 0;
    
    for(int row= 0; row<land[0].size(); row++){
        
        int sum = 0;
        vector<int> read ;
        for(int col = 0; col < land.size(); col++){
            if(land[col][row]==0) continue;
            auto f = find(read.begin(),read.end(),land[col][row]);
            if(f!= read.end()) continue;
            read.push_back(land[col][row]);
            sum += dummy[land[col][row]];    
        }
        if(answer <= sum)answer = sum;
    }
    
    return answer;
}

 

 

마무리하며

내가만들었지만.. 잘만든것 같아.! 다른 풀이를 보니 재귀도 있고 아닌것도 있는 것 같다. 여러가지 보았지만,재귀로 푸는게 가장 깔끔하다.

이전에 Level3 에서 혹독하게 후드려맞고 오는길이라 속상했는데, 이 문제 덕분에 편히 잘 수 있겠다. 

재귀를 별로 좋아하는 편은 아니다.무한루프에 빠져서 프로그램이 먹통되는게 싫었다. 그렇지만 필요한 곳에 사용하면 재귀만큼 편한게 없다