[백준/Node.js] 1987 알파벳

#DFS #백트래킹 #Set 

이 문제는 DFS와 백트래킹을 조합하여 간단히 풀 수 있는 문제이다. 

• 시작점은 0, 0이고, 말이 지나는 칸은 시작점도 포함이므로 초기 count는 1이다
• visitedWord에 알파벳을 기록해서 다시는 방문하지 않게 했다. DFS 탐색 중에 새롭게 방문한 칸의 알파벳이 visitedWord에 없으면 방문하고, 이미 있으면 탐색하지 않고 다른 방향으로 이동한다.  
• 백트래킹 과정에서, 탐색이 끝난 후에는 visitedWord에서 해당 알파벳을 지워줘야 한다. 다른 경로에서 같은 알파벳을 다시 사용할 수 있어야 하기 때문이다. 이렇게 백트래킹을 통해 탐색이 끝난 후에는 원래 상태로 돌아가서 다른 경로를 탐색할 수 있게 한다. 
• 탐색 중에 count 값을 갱신하면서 최대 칸 수를 기록한다. 

 

 

const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
const [R, C] = input.shift().split(" ").map(Number);
const map = input.map((row) => row.split(""));

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

let visitedWord = new Set();
let maxCount = 0;

function DFS(x, y, count) {
  visitedWord.add(map[x][y]);
  maxCount = Math.max(maxCount, count);

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

    if (
      nx >= 0 &&
      ny >= 0 &&
      nx < R &&
      ny < C &&
      !visitedWord.has(map[nx][ny])
    ) {
      DFS(nx, ny, count + 1);
    }
  }

  visitedWord.delete(map[x][y]);
}

DFS(0, 0, 1);
console.log(maxCount);

---

Set

Set은 JavaScript에서 제공하는 내장 객체 중 하나로, 중복되지 않는 값들의 컬렉션을 관리하는 자료 구조이다. 동일한 값을 여러 번 추가해도 하나의 값만 저장된다.

• 중복된 값 저장 불가
• 순서 보장 안됨
• Set은 내부적으로 hash table과 유사한 구조를 사용하여 값의 추가, 삭제, 검색이 O(1)의 시간 복잡도를 가진다. 

사용법을 간단히 알아보자. 

const mySet = new Set();

// 추가
mySet.add(1);
mySet.add(5);
mySet.add(1);  // 중복된 값은 무시됨
console.log(mySet);  // Set { 1, 5 }

 

// 삭제
mySet.delete(1);  // 값 1 삭제
console.log(mySet);  // Set { 5 }

 

// 값 포함 여부 확인
console.log(mySet.has(5));  // true
console.log(mySet.has(1));  // false

// 크기
console.log(mySet.size);  // 1

// 모든 값 제거
mySet.clear();
console.log(mySet);  // Set {}

 

활용

배열에서 중복을 제거할 때 유용하게 사용할 수 있다. 

const arr = [1, 2, 2, 3, 4, 4, 5];
const uniqueArr = [...new Set(arr)];
console.log(uniqueArr);  // [1, 2, 3, 4, 5]

 

또한 집합 연산에도 유용한데,

교집합

const setA = new Set([1, 2, 3]);
const setB = new Set([2, 3, 4]);
const intersection = new Set([...setA].filter(x => setB.has(x)));
console.log(intersection);  // Set { 2, 3 }

합집합

const union = new Set([...setA, ...setB]);
console.log(union);  // Set { 1, 2, 3, 4 }

차집합

const difference = new Set([...setA].filter(x => !setB.has(x)));
console.log(difference);  // Set { 1 }