[Java/C++] 프로그래머스 Level 2 - 석유 시추(PCCP 기출문제 2번)

문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

PCCP가 뭔진 모르겠는데, 갑자기 이와 관련된 기출문제가 많이 뜨더라.
그래서 하나 풀어봤다.

문제 이해 자체는 간단하고, 범위도 그렇게 넓지 않아서 쉽게 풀릴 줄 알았다.
근데 시간초과가 떠서 좀 애먹었다.

 

---

문제 핵심 및 풀이

---

석유 그룹화

해당 문제의 핵심은 상하좌우로 연결되어 있는 석유를 하나의 덩어리로 보는 것이다.

이는 land [][]의 값이 1인 곳부터 시작하여,
상화좌우로 연결된 곳이 하나도 없을 때까지 탐색하는 과정을 반복하면 된다.

이는 BFS 혹은 DFS를 사용하면 쉽게 확인할 수 있다.
나는 BFS를 통해 이를 확인하였다.

 

---

석유 덩어리를 얻을 수 있는 시추관의 위치

이 문제에서의 또 다른 특징은 시추관이 하나의 열을 관통한다는 것이다.
즉 이를 그래프로 봤을 때, x축은 전혀 고려하지 않는다.

이를 석유 덩어리 입장에서 보자.
시추관에 의에 채굴되려면 어떤 조건이 맞아야 할까?

만약 시추관이 있는 위치가 y = k이라면,
석유 덩어리 중, 딱 하나만이라도 y 좌표가 k이면 된다!

그래서 석유 덩어리를 그룹화할 때, 이 y 좌표의 정보들을 모아두기로 했다.

Set 집합 안에 해당 석유 덩어리의 모든 y 좌표를 보관한다.

시추관을 통해 채굴할 때, 시추관의 현재 y 위치와 석유 덩어리의 Set 집합을 비교한다.
만약 Set 집합 안에 y 위치가 포함되어 있다면, 이 석유 덩어리를 얻을 수 있다는 것이다.

이런 방식으로 해당 위치에서 얻을 수 있는 석유 덩어리를 알 수 있다.

 

---

실수하기 쉬운 부분

---

효율성 테스트 시간 초과

bfs를 통해 석유 덩어리를 그룹 한 뒤,
모든 열에 대해 석유 시추를 진행하면 시간 초과를 당할 것이다.

500 x 500 밖에 안 돼서, 당연히 시간초과 안 날 줄 알았는데..
그래서 어쩔 수 없이 로직을 바꿀 수밖에 없었다.

바꾼 방식은 각 열에서 시추한 석유의 총량을 해당하는 배열 인덱스에 저장하는 것

예를 들어서, 시추관이 0번 열 위치에서 얻은 석유 덩어리의 총량은 arr [0]에 저장된다.
그리고 4번 열 위치에서 얻는 석유 덩어리의 총량은 arr [4]에 저장된다.

이런 식으로 계산한다면, 시간초과가 발생하지 않고 해결할 수 있다.

 

---

코드 구현

---

C++ 구현 코드

↓

#include <string>
#include <vector>
#include <set>
#include <queue>
using namespace std;

// 석탄 덩어리 구조체 
struct Group{
    int count;
    set<int> possibleY;
};

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int height,width;
bool visited[500][500];
vector<vector<int>> map; // 맵
vector<Group> groups; // 석탄 덩어리 그룹

//반환하는 것은 석탄 덩어리
Group bfs(int sx, int sy){
    queue<pair<int,int>> q;
    set<int> possibleY;
    q.push({sx,sy});
    possibleY.insert(sy);
    visited[sx][sy] = true;
    int count = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= height || ny >= width 
               || map[nx][ny] == 0 || visited[nx][ny]) continue;
            visited[nx][ny] = true;
            q.push({nx,ny});
            count++;
            possibleY.insert(ny);
        }
    }
    return {count,possibleY};
}

void init(vector<vector<int>> land){
    map = land;
    height = land.size();
    width = land[0].size();
    
    for(int i = 0; i < land.size(); i++){
        for(int j = 0; j < land[i].size(); j++){
        	// 석유가 없거나, 이미 방문한 땅이면 패스
            if(visited[i][j] || land[i][j] == 0) continue;
            groups.push_back(bfs(i,j));
        }
    }
}

int solution(vector<vector<int>> land) {
    init(land);
    int answer[501] = {0};
    int maxNum = 0;
    for(int i = 0; i < groups.size(); i++){
        for(auto it : groups[i].possibleY){
            answer[it] += groups[i].count;
            maxNum = max(maxNum,answer[it]);
        }
    }
    return maxNum;
}

 

---

Java 구현 코드

↓

import java.util.*;

class Solution {
    private int[] dx = {-1,1,0,0};
    private int[] dy = {0,0,-1,1};
    private List<Group> groups = new ArrayList<>();
    private int width,height;
    private boolean[][] visited;
    private int[][] land;
    
    public int solution(int[][] land) {
        int maxNum = 0;
        this.land = land;
        initGroups(land);
        int[] answer = new int[land[0].length];
        
        // 모든 석유 덩어리를 확인해서, 시추 가능한 땅의 열에 모두 저장
        for(int i = 0; i < groups.size(); i++){
            for(Integer offset : groups.get(i).possibleY){
                answer[offset] += groups.get(i).count;
                maxNum = Math.max(maxNum,answer[offset]);
            }
        }
        return maxNum;
    }
    
    private void initGroups(int[][] land){
        visited = new boolean[land.length][land[0].length];
        height = land.length;
        width = land[0].length;
        
        for(int i = 0; i < land.length; i++){
            for(int j = 0; j < land[0].length; j++){
            	// 석유가 없는 땅이거나, 이미 방문한 땅이면 패스
                if(visited[i][j] || land[i][j] == 0) continue;
                groups.add(bfs(i,j));
            }
        }
    }
    
    // 최종적으로 만들어지는 것은 석유 덩어리
    private Group bfs(int sx, int sy){
        Queue<List<Integer>> q = new LinkedList<>();
        Set<Integer> possibleY = new HashSet<>();
        int count = 1;
        q.add(List.of(sx,sy));
        visited[sx][sy] = true;
        possibleY.add(sy);
        while(!q.isEmpty()){
            List<Integer> temp = q.poll();
            int x = temp.get(0);
            int y = temp.get(1);
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || ny < 0 || nx >= height || ny >= width
                  || land[nx][ny] == 0 || visited[nx][ny]) continue;
                
                visited[nx][ny] = true;
                q.add(List.of(nx,ny));
                count++;
                possibleY.add(ny);
            }
        }
        return new Group(possibleY,count);
    }
    
    // 석유 덩어리 그룹 클래스를 만듦
    public class Group{
        int count;
        Set<Integer> possibleY;
        public Group(Set<Integer> possibleY, int count){
            this.possibleY = possibleY;
            this.count = count;
        }
    }
}

 

---

시행착오

오랜만에 제대로 풀어본 문제, 그래도 스스로 풀었다.
시간초과 때문에 좀 걸리기 했지만..

그래도 푼 게 좋다.. ㅎ

Level 2라서 다행이다

 

 

https://toss.me/howudong

howudong님에게 보내주세요