[프로그래머스] PCCP 2번. 석유시추

 

 

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

프로그래머스

 

BFS나 DFS를 이용해 푸는 것은 바로 파악을 했다. 

그런데, 이 문제에서 고민해야 할 사항은 따로 있었다. 

 

• 어떻게 방문한 가로축 지역들을 보관할 것인가?
• 어떻게 가로축 데이터들을 누적처리할 것인가?

 

이를 위해 Set, js의 배열의 특성을 활용했다. 

JS의 배열의 원소는 타입이 같을 필요가 없다는 점과, 

Set을 이용해 방문한 모든 지역의 가로축 좌표를 담아도 중복이 없게 받을 수 있다는 점을 활용했다. 

 

const xMove = [-1, 1, 0, 0];
const yMove = [0, 0, -1, 1];

function calculateAccumulated(land, x, y) {
  const stack = [];
  const visited = Array.from({ length: land.length }, () =>
    Array(land[0].length).fill(false)
  );
  stack.push([x, y]);
  const yAreas = new Set();
  yAreas.add(y);
  let total = 0;
  while (stack.length !== 0) {
    const [sourceX, sourceY] = stack.pop();
    if (visited[sourceX][sourceY]) continue;
    visited[sourceX][sourceY] = true;
    land[sourceX][sourceY] = 0;
    total++;
    for (let index = 0; index < 4; index++) {
      const nextX = sourceX + xMove[index];
      const nextY = sourceY + yMove[index];
      if (
        nextX < 0 ||
        nextX >= land.length ||
        nextY < 0 ||
        nextY >= land[0].length
      )
        continue;
      if (visited[nextX][nextY]) continue;
      if (land[nextX][nextY] == 0) continue;
      stack.push([nextX, nextY]);
      yAreas.add(nextY);
    }
  }
  return [total, Array.from(yAreas)];
}

 

이런식으로 DFS를 이용해 한 묶음으로 존재할 석유들의 총 합과, 가로축 좌표들을 구했다. 

 

let totalCount;

function solution(land) {
  totalCount = new Array(land[0].length).fill(0);
  for (let x = 0; x < land.length; x++) {
    for (let y = 0; y < land[0].length; y++) {
      if (land[x][y] == 0) continue;
      const [total, yAreas] = calculateAccumulated(land, x, y);
      for (let yArea of yAreas) {
        totalCount[yArea] += total;
      }
    }
  }

  return Math.max(...totalCount);
}

이렇게 메인함수를 만들었다. 

석유들의 합을 누적배열에 더해주어, 누적배열의 최댓값을 반환하는 방식으로 문제를 풀었다. 

 

실행 자체는 다 되었지만, 

효율성에서 떨어졌다. 

 

코드의 수행시간이 왜 길어질까를 고민하다가, 

const visited = Array.from({ length: land.length }, () =>
    Array(land[0].length).fill(false)
  );

이 부분이 문제가 있음을 느꼈다. 

함수를 실행할 때 마다 2차원 배열을 초기화하고 사용해야하는 문제가 있다. 

 

하지만, 우리의 문제는 방문한 지역들을 0으로 바꿔버리면 되기 때문에

굳이 visited를 처리해줄 필요가 없다. 

 

function calculateAccumulated(land, x, y) {
  const stack = [];
  const yAreas = new Set();
  stack.push([x, y]);
  yAreas.add(y);
  let total = 0;
  while (stack.length !== 0) {
    const [sourceX, sourceY] = stack.pop();
    if (land[sourceX][sourceY] === 0) continue; // 이미 방문한 지점은 스킵
    land[sourceX][sourceY] = 0; // 방문한 지점 표시
    total++;
    for (let index = 0; index < 4; index++) {
      const nextX = sourceX + xMove[index];
      const nextY = sourceY + yMove[index];
      if (
        nextX < 0 ||
        nextX >= land.length ||
        nextY < 0 ||
        nextY >= land[0].length
      )
        continue;
      if (land[nextX][nextY] == 0) continue;
      stack.push([nextX, nextY]);
      yAreas.add(nextY);
    }
  }
  return [total, Array.from(yAreas)];
}

 

이런식으로 방문처리를 없애고 문제를 다시 풀어보았다. 

그랬을 때 효율성 검사의 문제 없이 문제 해결을 성공했다. 

 

---

배운점

방문을 더욱 효율화시키기 위한 방안을 생각해야겠다는 생각이 들었다. 

visited를 2차원 배열로 처리하지 않고 해결할 방법이 있을까?

차라리 방문을 2차원 배열로 전부 만드는게 아니라,

방문한 지역들만을 담는 연결리스트같은 것을 쓰는것은 어떨까?

나중에 효율성 테스트를 다 돌려봐야겠다.