[프로그래머스 PCCP 기출] 석유시추 js javascript (시간초과)

 

가장 많은 석유를 시추할 수 있는 열을 찾아야 하는 문제 

지나가는 석유 덩어리 전부를 추출해야 하므로 너비 검색을 위해 bfs를 사용했다. 

 

 

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

프로그래머스

 

 

정확도 테스트는통과했으나 효율성 부분 4개테스트에서 시간초과가 발생했다. 

gpt4o의 힘을 빌려봐도 마땅한 답이 나오지 않는다... 역시 파이썬이 답인가............

function solution(land) {
    var answer = 0;
    var col = land[0].length;
    var row = land.length;
    
    var visited = Array.from({ length: row }, () => Array(col).fill(false)); // 외부에서 초기화
    
    const bfs = (land, visited, start) => {
        var directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]; // 상하좌우
        var queue = [start];
        visited[start[0]][start[1]] = true; // 시작점을 방문 처리
        let oilCheck = 1;
        
        while (queue.length > 0) {
            const [x, y] = queue.shift(); // 선입선출 방식으로 꺼내기 
            for (let [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;
                if (nx >= 0 && nx < land.length && ny >= 0 && ny < land[0].length && !visited[nx][ny] && land[nx][ny] === 1) {
                    queue.push([nx, ny]);
                    visited[nx][ny] = true;
                    oilCheck++;
                }
            }
        }
        return oilCheck;
    };
    
    // 석유 크기 계산
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (land[i][j] === 1 && !visited[i][j]) {
                bfs(land, visited, [i, j]);
            }
        }
    }
  
    const getMaxSize = (colIndex) => {
        let maxSize = 0;
        let visited = Array.from({ length: row }, () => Array(col).fill(false)); // 초기화
        for (let i = 0; i < row; i++) {
            if (land[i][colIndex] === 1 && !visited[i][colIndex]) {
                maxSize += bfs(land, visited, [i, colIndex]);
            }
        }
        return maxSize;
    };
    
    for (let j = 0; j < col; j++) { // 열을 탐색
        let res = getMaxSize(j);
        if (res > answer) answer = res;
    }
    
    return answer;
}

답이 나올때까지 좀 더 고민해봐야겠다.