Set 를 이용한 방문처리 (G4 샘터)

문제 18513 샘터

18513번: 샘터

💡 입력
첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ 100,000,000) 단, 모든 N개의 샘터의 위치들은 서로 다르게 주어진다.

풀이

샘물 위치를 큐에 넣고 1만큼 떨어진 주변을 탐색하여 값을 도출한다. 너비우선탐색을 사용하여 쉽게 풀이법을 찾을 수 있었다.

문제

하지만 방문처리를 하기 위해 배열을 길이를 선언해야 했다. 그러나, 샘터의 위치가 -1억부터 +1억까지의 총 2억 범위에 있기 때문에 메모리 초과 문제가 발생했다.

const visited = Array.from({ length: 200_000_000 }, () => false); // 🚨 메모리 초과

또한 집을 지을 수 있는지 위치 범위가 샘터의 위치 범위와 같다고 문제에서 볼 수 없기 때문에 방문 배열의 길이를 미리 선언하는 것은 옳지 않았다.

해결

따라서 배열대신 Set 자료구조를 사용하여 문제를 해결하였다.

set.add() 메서드를 사용하여 방문처리를 하고 set.has() 메서드를 통해 방문여부를 확인할 수 있다.

set.has() 의 시간 복잡도는 평균적으로 O(1) 이다. 이는 Set이 해시 테이블을 기반으로 구현되어 있기 때문에 해시 테이블을 사용하면 값의 존재 여부를 빠르게 확인할 수 있다.

코드

const dx = [-1, 1];

const [N, K] = inputArr.shift().split(" ").map(Number);
const arr = inputArr.shift().split(" ").map(Number);

const set = new Set(); // Set 선언

let house = 0;
let answer = 0;
const dequeue = new Dequeue();
arr.forEach((v) => dequeue.push([v, 0]));
arr.forEach((v) => set.add(v)); // 방문 처리

let isBreak = false;

while (dequeue.getLength()) {
  const [curX, count] = dequeue.shift();

  for (let i = 0; i < 2; i++) {
    const nx = curX + dx[i];

    if (set.has(nx)) continue; // 방문 여부 확인

    dequeue.push([nx, count + 1]);
    set.add(nx); // 방문 처리
    house += 1;
    answer += count + 1;
    if (house === K) {
      isBreak = true;
      break;
    }
  }

  if (isBreak) break;
}

console.log(answer);

정리

그동안 배열을 선언해서만 방문처리를 하였는데 Set 으로도 방문처리 방법이 있다는 것을 알게 되었다. 좋은 해결법인 것 같다.