프로그래머스 [Lv. 2] 석유 시추 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(land) {
    const [n, m] = [land.length, land[0].length];
    
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < m;
    };
    
    // 열당 석유량을 저장할 배열
    let dp = Array(m).fill().map(() => 0);
    
    const bfs = (sr, sc) => {
        // 몇 번 열에서 석유를 뽑았는지 확인해줄 배열
        let visited = Array(m).fill().map(() => 0);
        
        const q = [[sr, sc]];
        visited[sc] = 1;
        // 석유량
        let volume = 1;
        
        while (q.length) {
            const [r, c] = q.shift();
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (isValid(nr, nc) && land[nr][nc] == 1) {
                    land[nr][nc] = 0;
                    volume += 1;
                    visited[nc] = 1;
                    q.push([nr, nc]);
                };
            };
        };
        
        for (let v = 0; v < m; v++) {
            if (visited[v]) {
                dp[v] += volume;
            };  
        };
        return
    };
    
    
    
    // 전체 반복
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < m; c++) {
            // 1이 아니면 pass
            if (!land[r][c]) {
                continue;
            };
            land[r][c] = 0;
            // bfs
            bfs(r, c);
        };
    };
    const answer = Math.max(...dp);
    return answer;
}

풀이 방법

1. 열마다 석유 덩어리를 저장하기 위해 배열을 만든다.
2. 전체를 반복하면서 석유 덩어리가 있는지 확인한다.
   1. 석유 덩어리를 발견하면 bfs를 이용해서 석유를 끝까지 탐색한다.
      1. 석유를 탐색하는 과정에서 열의 번호를 저장한다.
      2. 이 과정에서 visited를 이용한다.
   2. 탐색하는 과정에서 석유 덩어리의 크기를 volume에 1씩 더해주며 측정한다.
   3. visited를 순회하며 1인경우 해당 열에 석유 덩어리가 있다는 말이므로 dp에 volume을 더해준다.
3. 마지막으로 Math.max를 이용해서 dp중 최대 값을 반환한다.

느낀점

• 자주 실수하는 부분이 아래, 오른쪽 방향만 해도 계산이 충분하겠지 생각한다.
• 하지만 미로같이 생긴 석유 덩어리는 위, 왼쪽 방향도 고려해야 한다.
• 또 Math.max(a1, a2, a3)인데 배열을 통채로 넣는 실수를 한다.
  • Math.max(...[a1, a2, a3])라는 점을 명심하자.