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

알고리즘 문제풀이/프로그래머스

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

이제ise이제 2023. 12. 3. 01:39

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

using namespace std;

int N, M;

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool isInMap(int r, int c){
    if(r >= 0 && c >= 0 && r < N && c < M) return true;
    else return false;
}

int bfs(int r, int c, int num, vector<vector<int>>& land){
    int cnt{};
    
    queue<pair<int, int>> q;
    q.push({r, c});
    cnt++;
    land[r][c] = num;
    
    while(!q.empty()){
        r = q.front().first;
        c = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nr = r + dir[i][0];
            int nc = c + dir[i][1];
            
            if(!isInMap(nr, nc)) continue; // land를 벗어나면 패스
            if(land[nr][nc] > 1) continue; // 방문한 곳은 패스
            if(land[nr][nc] == 0) continue; // 석유가 아니면 패스

            q.push({nr, nc});
            cnt++;
            land[nr][nc] = num; // land 값을 직접 변경
        }
    }
    
    return cnt;
}

int solution(vector<vector<int>> land) {
    int answer = 0;

    N = land.size();
    M = land[0].size();
    
    int num = 2; // 몇 번째 석유 덩어리인지(2번부터 카운트 : land의 디폴트가 1과 0이라서)
    vector<int> vRes; // 메모이제이션
    vRes.push_back(0); // 0번째 스킵용 인풋
    vRes.push_back(1); // 1번째 스킵용 인풋
    
    // 석유 덩어리별 크기 파악하기 + 메모이제이션
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(land[i][j] == 1){ // 탐색 안 한 석유 덩어리일 때
                // bfs 탐색
                int cnt = bfs(i, j, num, land); // 석유 크기 탐색
                vRes.push_back(cnt); // num번째 석유의 크기 = cnt
                num++;
            }
        }
    }
    
    // 시추관 투입
    for(int j = 0; j < M; j++){
        int res{}; // j열의 석유 크기 합계용
        vector<int> checkNv; // 서로 다른 석유인지 판단용
        // 시추관 투입
        for(int i = 0; i < N; i++){
            // 탐색 완료된 석유 덩어리
            if(land[i][j] > 1){
                int n = land[i][j]; // 석유 덩어리 번호

                // n이 checkNv에 있는지(이미 크기를 확인한 석유인지 체크용도)
                auto it = find(checkNv.begin(), checkNv.end(), n);
                // 체크한 적 없는 석유라면
                if(it == checkNv.end()){
                    checkNv.push_back(n); // 체크 용도에 넣기
                    res += vRes[n];
                }
            }
        }
        answer = max(answer, res);
    }
    
    return answer;
}

[풀이 중 겪은 문제 상황]

6번 테스트 케이스를 틀렸는데 예외를 모르던 상황.

코드를 하나하나 뜯어보다가 문득 든 생각 : 석유가 석유를 품고 있으면?

[해결]

코드가 직전에 탐색한 석유와 현재 탐색하는 석유가 다른지만 판단했던 것이 문제

직전이 아니라 시추관이 투입된 열에서 탐색한 모든 석유와 비교했어야했다.

해당 부분을 고치자 마자 바로 해결됨.

추가로,

평소 쓰던 방문확인용 int map[최대크기][최대크기]를 만들고도 효율성 문제는 별 무리없이 통과됐는데,

질문하기 글을 좀더 보니까 방문용 배열을 따로 만들지말고 land값을 덮어씌우는 방식도 있었다.

land 값은 0이나 1만 가능 => 석유 덩어리 번호를 2이상으로 체크하면 문제 없음

원본 값을 건드는 건 좋아하는 스타일이 아니지만,

solution의 파라미터는 call by value로 받은 거니까 건드려도 되겠는데?

싶어서 정답 코드는 land로만 판단하는 방식으로 수정했다.

티스토리

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

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

목차