[Agorithm] 석유 시추 ( Programmers - PCCP 기출문제 2번 / Python, Javascript )

문제 설명

세로길이가 n 가로길이가 m 인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

 

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2 입니다.

 

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어 나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

 

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

 

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

 

 

 

---

 

 

 

제한사항

 

 

 

---

 

 

 

입출력 예

 

 

 

---

 

 

 

문제 풀이

 

 

 

python:

from collections import deque
 
def bfs(land, visit, x, y):
    visit[x][y] = 1
    count = 1
    queue = deque([[x, y]])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
 
    min_y = len(land[0]) - 1
    max_y = 0
 
    while queue:
        queue_x, queue_y = queue.popleft()
 
        if queue_y < min_y:
            min_y = queue_y
 
        if queue_y > max_y:
            max_y = queue_y
 
        for i in range(4):
            dir_x, dir_y = directions[i]
            pivot_x, pivot_y = queue_x + dir_x, queue_y + dir_y
            if len(land) - 1 >= pivot_x >= 0 and len(land[0]) - 1 >= pivot_y >= 0 and land[pivot_x][pivot_y] == 1 and visit[pivot_x][pivot_y] == 0:
                visit[pivot_x][pivot_y] = 1
                queue.append([pivot_x, pivot_y])
                count += 1
 
    return [count, min_y, max_y]
 
 
def solution(land):
    answer = [0 for _ in land[0]]
    visit = [[0 for _ in land[0]] for _ in land]
 
    for x in range(len(land)):
        for y in range(len(land[0])):
            if land[x][y] == 1 and visit[x][y] == 0:
                count, mix_y, max_y = bfs(land, visit, x, y)
                for i in range(mix_y, max_y + 1):
                    answer[i] += count
 
    return max(answer)

 

 

 

 

 

javascript:

class Queue {
    constructor() {
        this.items = [];
    }
 
    enqueue(element) {
        this.items.push(element);
    }
 
    dequeue() {
        return this.items.shift();
    }
 
    size() {
        return this.items.length;
    }
}
 
const bfs = (graph, visited, start) => {
    const [N, M] = start;
    let minY = M;
    let maxY = M;
    visited[N][M] = true;
 
    const queue = new Queue();
    queue.enqueue([N, M]);
 
    let oilSize = 1;
 
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    while (queue.size() !== 0) {
        const [qn, qm] = queue.dequeue();
 
        for (let i = 0; i < 4; ++i) {
            const [x, y] = directions[i];
            const nx = x + qn;
            const ny = y + qm;
 
            const bfsN = graph.length - 1;
            const bfsM = graph[0].length - 1;
            if (0 <= nx && nx <= bfsN && 0 <= ny && ny <= bfsM  && graph[nx][ny] === 1 && !visited[nx][ny]) {
                queue.enqueue([nx, ny]);
                visited[nx][ny] = true;
                oilSize++;
 
                if (ny < minY) {
                    minY = ny;
                }
 
                if (maxY < ny) {
                    maxY = ny;
                }
            }
        }
    }
 
    return [minY, maxY, oilSize]
}
 
const solution = (land) => {
 
    const N = land.length;
    const M = land[0].length;
    const visited = Array.from({length: N}, ()=> Array(M).fill(false));
    const oilSizeList = Array.from({length: M}, () => 0);
 
    for (let i = 0; i < N; ++i) {
        for (let j = 0; j < M; ++j) {
            if (land[i][j] === 1 && !visited[i][j] ) {
 
                const [start, end, oilSize] = bfs(land, visited, [i, j]);
 
                for (let i = start; i <= end; ++i) {
                    oilSizeList[i] += oilSize;
                }
            }
        }
    }
 
 
    return Math.max(...oilSizeList);
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

프로그래머스