[PCCP 기출문제] 2번 / 석유 시추 - Python/JavaScript

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

프로그래머스

 

[문제 간단 요약]

1. 행을 기준으로 열의 끝까지 시추를 뚫을 때 발견되는 석유의 범위를 구하는 문제

2. 각각의 석유 범위의 값을 알아야 함

3. 시추를 뚫을때 같은 범위의 석유를 만날 경우 한번만 석유의 양을 더해줘야 

 

[문제 해결 방안]

- DFS와 BFS를 통해 각 석유의 범위 값을 찾기

- 하나의 석유 범위를 찾을 때 어떤 행에서 만날 수 있는지 행 별로 범위를 더해주며 문제 해결

  - 석유 범위를 모두 구한 다음 석유의 전체 양을 구하는 방식을 사용 시 시간 초과 발생

 

[문제 해결 코드 - Python]

from collections import deque

def depth_oil(y, x, land, used, check_oil):
    directs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    q = deque()
    q.append((y, x))
    used[y][x] = 1
    oil=1
    min_x, max_x = x,x
    while q:
        y, x = q.popleft()
        for direct in directs:
            dy = y + direct[0]
            dx = x + direct[1]
            if dy < 0 or dx < 0 or dy > len(land) - 1 or dx > len(land[0]) - 1:continue
            if used[dy][dx] == 0 and land[dy][dx] == 1:
                min_x=min(min_x,dx)
                max_x=max(max_x,dx)
                used[dy][dx] = 1
                oil += 1
                q.append((dy, dx))
    for idx in range(min_x, max_x+1):
        check_oil[idx]+=oil
        

def solution(land):
    used = [[0]*len(land[0]) for _ in range(len(land))]
    check_oil = [0] * len(land[0])
    for y in range(len(land)):
        for x in range(len(land[0])):
            if land[y][x] == 1 and used[y][x] == 0:
                depth_oil(y, x, land, used, check_oil)
                
    return max(check_oil)

 

[문제 해결 코드 - JavaScript]

function bfs(y,x,land,used, check_oil) {
    const directs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    const q = [];
    q.push([y, x])
    used[y][x]=1
    let oil = 1
    let min_x = x, max_x = x
    while (q.length > 0) {
        const [y,x] = q.shift()
        for (const [direct_y,direct_x] of directs) {
            const dy = y + direct_y
            const dx = x + direct_x
            if (dy < 0 || dx < 0 || dy >= land.length || dx >=land[0].length) {continue;}
            if (used[dy][dx] === 0 && land[dy][dx]===1) {
                min_x = Math.min(min_x,dx);
                max_x = Math.max(max_x,dx);
                used[dy][dx] = 1;
                oil += 1;
                q.push([dy,dx])
            }
        }   
    }
    for (let idx = min_x; idx <= max_x; idx++) {
        check_oil[idx] += oil
    }
}

function solution(land) {
    const used = Array.from({ length: land.length }, () =>
        Array(land[0].length).fill(0)
    );

    const check_oil = Array(land[0].length).fill(0)
    for (y = 0 ; y < land.length; y++) {
        for (x=0; x < land[0].length; x++) {
            if (land[y][x] === 1 && used[y][x] === 0) {
                bfs(y,x,land,used, check_oil)
            }
        }
    }
    return Math.max(...check_oil)
}