석유 시추

프로그래머스 쉬운 문제인데 조금 헤맸다. 처음에는 단순한 탐색 문제인 줄 알고 풀었고 구현 하는 부분에서 내가 해석한대로 풀었더니 실패가 나와서 원인을 생각해보니 조건 문에서 분명히 뭔가 걸렸던 느낌이다.

SET 자료구조를 사용해서 더 쉽게 푸는 방법이 있다는 내용을 보고 응용했더니 바로 다 풀렸다.

처음에 저기 까만 곳에 보이는 도형의 크기를 DFS 로 구하고 각 컬럼마다 가장 많은 합을 구해야 하는데..각 컬럼마다 DFS 하는 방법보다는 미리 계산을 하고 MAP으로 컬럼마다 최대 값을 정해두었다.

이 후에는 SET를 사용해서 계산 후 쉽게 풀었다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

int blockNum = 2; 
bool visited[501][501]; 
map<int, int> hashMap; 

int dfs(int i, int j, vector<vector<int>>& land){
    if(i < 0 || j < 0 || i >= land.size() || j >= land[0].size() || visited[i][j] || land[i][j] == 0) return 0; 
    land[i][j] = blockNum; 
    visited[i][j] = true; 
    int count = 1; 
    
    count += dfs(i+1,j,land); 
    count += dfs(i-1,j,land);  
    count += dfs(i,j+1,land); 
    count += dfs(i,j-1,land); 
    
    return count; 
}

int solution(vector<vector<int>> land) {
    int answer = 0;
    memset(visited,false,sizeof(visited)); 
    for(int i = 0; i < land.size(); i++){
        for(int j = 0; j < land[0].size(); j++){
            if(land[i][j] != 0 && !visited[i][j]){
                int area = dfs(i,j,land); 
                hashMap[blockNum] = area; 
                blockNum++; 
            }
        }
    }
    
    for(int j = 0; j < land[0].size(); j++){
        //int currBlock = -1; 
        int currSum = 0; 
        set<int> s; 
        for(int i = 0; i < land.size(); i++){
            // if(land[i][j] != 0 && land[i][j] != currBlock){
            //     currBlock = land[i][j]; 
            //     currSum += hashMap[currBlock]; 
            // } 
            s.insert(land[i][j]); 
        }
        for(auto& it : s){
            currSum += hashMap[it]; 
        }
        answer = max(answer,currSum); 
    }
    
    
    return answer;
}