[Programmers] PCCP 기출문제 석유 시추 JS

📌 PCCP 기출문제 석유 시추

석유 시추 던전이 열렸다해서 무모하게 도전을 했습니다. 결국 돌아온건 두통🤕

실패(시간 초과)

function solution(land) {    
    const n = land.length;
    const m = land[0].length;
    
    const dx = [-1,1,0,0];
    const dy = [0,0,-1,1];
    
    let queue = []
    
    let oilCntCol = new Array(m).fill(0);
    
    for(let i=0;i<m;i++) {
        let copyLand = land.map(col => [...col]);
        let cnt = 0;
        
        for(let j=0;j<n;j++) {
            if(copyLand[j][i] === 1) {
                queue  = [[j,i]];
            
                while(queue.length>0) {
                    let [y,x] = queue.shift();
                
                    if(copyLand[y][x] === 1) {
                        copyLand[y][x] = 0;
                        cnt +=1;
                    
                        for(let k=0;k<4;k++) {
                            let nx = x + dx[k]
                            let ny = y + dy[k]
                        
                            if(nx >= 0 && ny >= 0 && nx < m && ny < n && copyLand[ny][nx] === 1) 
                            {
                                queue.push([ny,nx]);
                            }
                        }
                    }
                }
            }
        }
        oilCntCol[i] = cnt
    }
    return Math.max(...oilCntCol)
}

queue를 사용하여 모든 위치를 방문하여 석유의 존재 여부를 확인하여 값을 찾는 코드를 작성했습니다. 하지만 이 방식은 시간 복잡도가 높아 큰 데이터에서 효율적이지 않았고, 결국 시간 초과에 걸리고 말았습니다.

성공

function solution(land) {
    const n = land.length;
    const m = land[0].length;

    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    
    const oilCntCol = new Array(m).fill(0); 
    const visited = Array.from(Array(n), () => Array(m).fill(false));

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (land[i][j] === 1 && !visited[i][j]) {
                let cnt = 0;
                const queue = [[i, j]];
                visited[i][j] = true;
                const columnsInRegion = new Set(); 

                while (queue.length > 0) {
                    const [y, x] = queue.shift();
                    cnt += 1;
                    columnsInRegion.add(x); 

                    for (let k = 0; k < 4; k++) {
                        const nx = x + dx[k];
                        const ny = y + dy[k];

                        if (nx >= 0 && ny >= 0 && nx < m && ny < n && land[ny][nx] === 1 && !visited[ny][nx]) {
                            queue.push([ny, nx]);
                            visited[ny][nx] = true;
                        }
                    }
                }
                columnsInRegion.forEach(col => {
                    oilCntCol[col] += cnt;
                });
            }
        }
    }
    return Math.max(...oilCntCol);
}

위에서 시간 초과로 실패한 코드를 수정했습니다.

1. visited 배열 추가: 시간 초과를 피하기 위해 방문 여부를 확인하는 visited 배열을 추가하여, 한 번 방문한 위치는 다시 방문하지 않음. 이를 통해 중복 방문을 방지하고 효율성을 높였습니다.

2. 석유 탐색 시 같은 구역 내 열(column) 정보 추적: Set을 사용해 현재 석유 구역에 해당되는 열을 기록하고, 그 열들에 대한 석유 카운트를 업데이트했습니다. 즉, 각 구역의 석유량을 한 번에 기록하여 중복 계산을 줄였고, 특정 열의 석유량을 합산하는 작업을 최적화했습니다.

3. 구역 내 연결된 모든 석유 탐색 후 반영: BFS로 완전히 탐색한 후 columnsInRegion 열들에 대해 탐색한 석유량 cnt를 추가해 줍니다. 이로써 각 구역의 석유량을 정확하게 기록할 수 있게 되었습니다.

도움을 주신 감자전님의 냄피욘 감사합니다. 🙇🏻