자바스크립트로 보는 DFS

DFS는 어떤 알고리즘인가?

DFS는 depth-first-search의 줄임말로 그래프에서 깊이를 우선적으로 탐색하는 알고리즘이다.
이때 그래프는 정점(node)와 간선(edge)으로 구성된 자료구조로, 정점이 목적지라면 간선은 목적지를 잇는 경로를 의미한다.
깊이를 우선적으로 탐색한다는 것은 한 방향으로 끝까지 파고들었다가 더 이상 갈 곳이 없을 때 되돌아온다는 것을 의미한다.

DFS는 언제 쓰는가?

DFS는 모든 경로를 탐색해야 하는 경우에 적합하다. (그래프 연결 요소, 백트래킹, 트리 탐색)

DFS는 한 방향으로 끝까지 파고들기 때문에 최단 경로 문제를 푸는 데에는 부적합하다.
이때는 BFS를 사용하는 것이 적합하다.

여기서 백트래킹은 가능성이 없는 경로는 더 깊이 탐색하지 않고 되돌아가는 기법이다.
DFS는 기본적으로 모든 경로를 다 탐색하지만 백트래킹은 특정 조건에 맞지 않으면 중단할 수 있어 DFS + 불필요한 탐색 제거 => 백트래킹 이라고 생각할 수 있다.

백트래킹은 기본적으로 아래와 같은 구조를 가지는데, 불가능한 경우에 일찍 탐색을 중단하고 이전 선택을 취소하여 다음 선택지로 탐색할 수 있도록 한다.

function backtrack(depth) {
  if (불가능한 상태) return;   // ⭐ 가지치기

  if (완성 조건) {
    정답 처리;
    return;
  }

  for (선택지) {
    선택;
    backtrack(depth + 1);
    선택 취소; // ⭐ 되돌리기
  }
}

백트래킹을 활용하여 순열, 조합, 부분집합, N-Queen 등의 문제를 풀 수 있다.

순열

const arr = [1, 2, 3];
const visited = Array(3).fill(false);
const path = [];

function dfs() {
  if (path.length === 3) {
    console.log(path.join(' '));
    return; // 완성 조건에 맞는 경우 중단
  }

  for (let i = 0; i < 3; i++) {
    if (visited[i]) continue;

    visited[i] = true;
    path.push(arr[i]);

    dfs();

    path.pop();          // 되돌리기
    visited[i] = false;  // 되돌리기
  }
}

dfs();

조합 (i=start 부터 시작하는 것이 포인트)

const arr = [1, 2, 3, 4];
const r = 2;
const path = [];

function dfs(start){
  if(path.length === r){
    console.log(path.join(' '))
    return; // 완성 조건에 맞는 경우 중단
  }

  for(let i=start;i<arr.length;i++){
    path.push(arr[i])
    dfs(i+1)
    path.pop() // 되돌리기
  }
}

dfs(0);

부분 집합

const arr = [1, 2, 3];
const result = [];
const path = [];

function dfs(idx) {
  if (idx === arr.length) {
    result.push([...path]);
    return;
  }

  // 현재 원소 선택
  path.push(arr[idx]);
  dfs(idx + 1);

  // 선택 취소
  path.pop();
  dfs(idx + 1);
}

dfs(0);
console.log(result);

DFS는 어떻게 구현하는가?

DFS를 구현하는 방식은 크게 두 가지 방식이 있다.
첫 번째는 재귀를 이용하는 방법이고, 두 번째는 스택을 이용하는 방법이다.

재귀를 이용한 구현

인자로 필요한 것은 그래프, 탐색할 노드, 방문 여부 배열인데, 한 번 방문한 노드는 다시 방문하지 않도록 방문 여부를 나타내는 배열이 꼭 필요하다. (+ 무한 루프 방지)

깊이를 우선적으로 탐색하기 위해 특정 노드와 연결된 노드들을 재귀로 탐색한다.
재귀를 이용하여 구현했을 때의 단점은 깊이가 매우 깊을 경우 스택 오버플로우가 발생할 수 있다는 것이다.

function dfs(graph, node, visited) {
  visited[node] = true;
  console.log(node);

  for (const next of graph[node]) {
    if (!visited[next]) {
      dfs(graph, next, visited);
    }
  }
}

스택을 이용한 구현

스택을 이용하여 구현했을 때는 스택 오버플로우가 발생할 위험성은 줄어들지만 그래프를 탐색하는 순서가 재귀를 이용한 방식과는 조금 달라질 수 있다.

const stack = [start];
visited[start] = true;

while (stack.length) {
  const node = stack.pop();
  console.log(node);

  for (const next of graph[node]) {
    if (!visited[next]) {
      visited[next] = true;
      stack.push(next);
    }
  }
}

예를 들어 아래의 트리를 재귀를 이용한 방식으로 탐색한다면 2 -> 5 -> 9 -> 4 -> 7 -> 2 -> 6 -> 5 -> 11 순서로 탐색하게 될 것이다. (트리가 오름차순으로 정렬되어 있다는 가정하에)
그러나 스택을 이용한 방식으로 탐색한다면 2 -> 7 -> 6 -> 11 -> 5 -> 2 -> 5 -> 9 -> 4 순서로 탐색하게 될 것이다. 왜냐면 스택에 연결된 노드를 다 넣고 가장 마지막 요소를 pop하여 탐색하기 때문에 더 높은 숫자를 먼저 탐색하게 되는 것이다.
이 방식도 틀린 것은 아니지만 보통 사전순으로 탐색을 하기 때문에 알아두고 있는 것이 좋다.

관련 문제 풀어보기

[백준] 로또

• 난이도 : 실버 2
• 문제 링크 : https://www.acmicpc.net/problem/6603

길이가 6인 조합 구하기

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const LOTTO_COUNT = 6;
const answer = [];

function dfs(arr, start, path){
  if(path.length === LOTTO_COUNT){
    answer.push(path.join(' '))
    return;
  }

  for(let i=start;i<arr.length;i++){
    path.push(arr[i])
    dfs(arr, i+1, path)
    path.pop();
  }
}

for(let i=0;i<input.length-1;i++){
  const arr = input[i].split(' ').map(Number).slice(1);
  const path = [];

  dfs(arr, 0, path);

  if(i !== input.length -2) answer.push('')
}

console.log(answer.join('\n'));

[백준] 양팔저울

• 난이도 : 실버 1
• 문제 링크 : https://www.acmicpc.net/problem/17610

측정할 수 있는 물의 무게는 두 저울 사이의 차(절댓값)와 같다.
저울을 물 반대편에 올릴 수도 있고(+), 물 쪽에 올릴 수도 있고(-), 안 올릴 수도 있으므로(0) 세 가지의 연산을 반복해주며 모든 저울을 탐색하면 된다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const K = +input[0]
const arr = input[1].split(' ').map(Number);
const S = arr.reduce((acc,cur) => acc+cur,0);
const answer = Array(S+1).fill(false);
const visited = Array.from({length: K+1}, () => Array(S*2+1).fill(false));

function dfs(i, diff){
  if(i === K){
    answer[Math.abs(diff)] = true;
    return;
  } 

  if(visited[i][diff + S]) return;
  visited[i][diff + S] = true;

  dfs(i+1, diff + arr[i])
  dfs(i+1, diff - arr[i])
  dfs(i+1, diff)
}

dfs(0, 0)

console.log(answer.filter(v => !v).length)

자바스크립트로 시간 초과가 발생해서 dp + set 조합으로 변경해서 통과했다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const K = +input[0]
const arr = input[1].split(' ').map(Number);
const S = arr.reduce((acc,cur) => acc+cur,0);

let dp = new Set([0]);

for (const w of arr) {
  const next = new Set(dp);

  for (const diff of dp) {
    next.add(diff + w);
    next.add(diff - w);
  }

  dp = next;
}

const possible = Array(S + 1).fill(false);

for (const diff of dp) {
  const d = Math.abs(diff);
  if (d <= S) possible[d] = true;
}

let count = 0;
for (let i = 1; i <= S; i++) {
  if (!possible[i]) count++;
}

console.log(count);

[백준] 촌수계산

• 난이도 : 실버 2
• 문제 링크 : https://www.acmicpc.net/problem/2644

가족 관계에서 계층이 명확하고 계층 간 이동해야 하는 횟수를 구해야 하므로 명확한 dfs 문제이다.
가족 관계를 그래프로 나타내고, 타겟을 찾을 때까지 depth를 증가시키며 이동하면 된다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
const [N1, N2] = input[1].split(' ').map(Number);
const M = +input[2];
const tree = Array.from({length: N+1}, () => [])
const visited = Array.from({length: N+1}, () => false)
let answer = -1;

for(let i=3;i<3+M;i++){
  const [parent, child] = input[i].split(' ').map(Number);
  tree[parent].push(child)
  tree[child].push(parent)
}

function dfs(n, depth){
  visited[n] = true;

  if(n === N2){
    answer = depth;
    return;
  }

  for(let node of tree[n]){
    if(!visited[node]){
      dfs(node, depth+1)
    }
  }
}

dfs(N1, 0);

console.log(answer);

[백준] 물통

• 난이도 : 골드 4
• 문제 링크 : https://www.acmicpc.net/problem/2251

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [A, B, C] = input[0].split(' ').map(Number);
const visited = Array.from({length: A+1}, () => Array.from({length: B+1}, () => false))
const answer = new Set();

function dfs(a,b){
  if (visited[a][b]) return;
  visited[a][b] = true;

  const c = C - a - b;

  if(a === 0){
    answer.add(c)
  }

  let move;

  // A → B
  move = Math.min(a, B - b);
  dfs(a - move, b + move);

  // A → C
  move = Math.min(a, C - c);
  dfs(a - move, b);

  // B → A
  move = Math.min(b, A - a);
  dfs(a + move, b - move);

  // B → C
  move = Math.min(b, C - c);
  dfs(a, b - move);

  // C → A
  move = Math.min(c, A - a);
  dfs(a + move, b);

  // C → B
  move = Math.min(c, B - b);
  dfs(a, b + move);
}

dfs(0,0)

console.log([...answer].sort((a,b) => a-b).join(' '));

[백준] 트리

• 난이도 : 골드 4
• 문제 링크 : https://www.acmicpc.net/problem/4803

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
let idx = 0;
const answer = [];
let testcase = 1;

function dfs(node, parent, graph, visited){
  visited[node] = true;

  for (const next of graph[node]) {
    if (!visited[next]) {
      // 자식 쪽에서 사이클 발견되면 중단
      if (!dfs(next, node, graph, visited)) {
        return false;
      }
    }
    // 방문했는데 부모 요소가 아니면 사이클
    else if (next !== parent) {
      return false;
    }
  }

  return true;
}

while(true){
  const [N,M] = input[idx++].split(' ').map(Number);
  if(N === 0 && M === 0) break;

  const graph = Array.from({length:N+1}, () => []);
  const visited = Array(N + 1).fill(false);

  for(let i=0;i<M;i++){
    const [s, e] = input[idx++].split(' ').map(Number);
    graph[s].push(e)
    graph[e].push(s)
  }

  let treeCount = 0;

  // 모든 연결 요소 탐색
  for (let i = 1; i <= N; i++) {
    if (!visited[i]) {
      if (dfs(i, 0, graph, visited)) treeCount++;
    }
  }
  
  if(treeCount === 0){
    answer.push(`Case ${testcase}: No trees.`)
  }else if(treeCount === 1){
    answer.push(`Case ${testcase}: There is one tree.`)
  }else{
    answer.push(`Case ${testcase}: A forest of ${treeCount} trees.`)
  }

  testcase++;
}

console.log(answer.join('\n'));

[백준] 알파벳

• 난이도 : 골드 4
• 문제 링크 : https://www.acmicpc.net/problem/1987

방문 여부 체크를 아래처럼 나누어 했다.
1. 좌표 방문 여부
2. 알파벳 방문 여부
이때 알파벳은 대문자 알파벳만 체크하면 되므로 사이즈를 26으로 해주고, A의 아스키코드가 65이기 때문에 알파벳.charCodeAt() - 65 위치에 방문 여부를 체크하면 된다.

상하좌우로 이동하며 아래와 같은 경우는 탐색을 하지 않는다.
1. 좌표 범위를 벗어나는 경우
2. 이미 방문한 알파벳일 경우
3. 이미 방문한 좌표일 경우

탐색 후 다른 경로로 다시 지나갈 수 있기 때문에 백트래킹으로 방문 여부를 해제해주어야 한다.

시작점을 포함하여 최대한 지나갈 수 있는 칸 수를 구해야 하므로 1부터 depth가 깊어질수록 1씩 더해준다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [R, C] = input.shift().split(' ').map(Number);
const visited = Array.from({length: R+1}, () => Array(C+1).fill(false)); // 좌표 방문 여부
const alphabet_visited = Array(26).fill(false); // 알파벳 방문 여부
const move = [[0,1], [0,-1], [-1,0], [1,0]];
let answer = 0;

function dfs(x,y,d){
  if(visited[x][y]) return;

  visited[x][y] = true;
  const alphabet = input[x][y].charCodeAt() - 65;
  alphabet_visited[alphabet] = true;

  for(let [mx, my] of move){
    const nx = x+mx;
    const ny = y+my;

    if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
    const nextAlphabet = input[nx][ny].charCodeAt() - 65;
    if(alphabet_visited[nextAlphabet]) continue;
    if(!visited[nx][ny]) dfs(nx,ny,d+1)

    visited[nx][ny] = false;
    alphabet_visited[nextAlphabet] = false;
  }

  if(d > answer) answer = d
}

dfs(0,0,1)

console.log(answer);

위의 풀이로 맞긴 했지만 비효율적인 부분과 잘못 짜여진 부분이 있어 아래처럼 개선했다.

개선점
1. 좌표 방문 여부는 안 쓰고 알파벳 방문 여부만 체크하면 된다. 이미 방문한 좌표는 알파벳에 체크가 되어 있기 때문에 중복으로 체크할 필요가 없다.
2. dfs가 호출되지 않아도 방문 여부를 해제하지 않는 형태인데, 좀 더 안정적인 구조로 만들기 위해 dfs 직전에 방문 여부를 체크하고, dfs 후에 방문 여부를 해제하도록 한다.
3. 답을 갱신하는 부분도 최상단으로 올려준다.
4. 매번 charCodeAt을 호출하지 않고 초기에 보드에 있는 알파벳을 모두 숫자로 바꾸어두면 편리하다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [R, C] = input.shift().split(' ').map(Number);
const board = input.map(row =>
  [...row].map(c => c.charCodeAt(0) - 65)
);
const visited = Array(26).fill(false); // 알파벳 방문 여부
const move = [[0,1], [0,-1], [-1,0], [1,0]];
let answer = 0;

visited[0][0] = true;

function dfs(x,y,d){
  answer = Math.max(answer, d)

  for(let [mx, my] of move){
    const nx = x+mx;
    const ny = y+my;

    if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
    
    const nextAlphabet = board[nx][ny];
    if(visited[nextAlphabet]) continue;
    
    visited[nextAlphabet] = true; // 선택
    dfs(nx,ny,d+1) // 재귀
    visited[nextAlphabet] = false; // 복구
  }
}

dfs(0,0,1)

console.log(answer);

[백준] 영역 구하기

• 난이도 : 실버 1
• 문제 링크 : https://www.acmicpc.net/problem/2583

보통은 왼쪽 상단 좌표가 (0,0)인데 문제에서는 왼쪽 하단 좌표가 (0,0)으로 주어져서 보드를 나타낼 때 M, N을 바꾸어서 설정했다.
우선 주어진 직사각형 범위를 1로 모두 표시하고 DFS로 모든 좌표를 탐색하며 영역의 넓이를 구했다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [M, N, K] = input[0].split(" ").map(Number);
const board = Array.from({ length: N }, () => Array(M).fill(0));
const move = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];
const visited = Array.from({ length: N }, () => Array(M).fill(false));
const answer = [];

for (let i = 1; i <= K; i++) {
  const [x1, y1, x2, y2] = input[i].split(" ").map(Number);
  const sx = x1 > x2 ? x2 : x1;
  const bx = x1 > x2 ? x1 : x2;
  const sy = y1 > y2 ? y2 : y1;
  const by = y1 > y2 ? y1 : y2;

  for (let i = sx; i < bx; i++) {
    for (let j = sy; j < by; j++) {
      board[i][j] = 1;
    }
  }
}

function DFS(x, y) {
  let area = 1;

  for (let [dx, dy] of move) {
    const nx = x + dx;
    const ny = y + dy;

    if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
    if (visited[nx][ny]) continue;
    if (board[nx][ny] === 1) continue;

    visited[nx][ny] = true;
    area += DFS(nx, ny);
  }

  return area;
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (!visited[i][j] && board[i][j] === 0) {
      visited[i][j] = true;
      const area = DFS(i, j);
      answer.push(area);
    }
  }
}

console.log(answer.length);
console.log(answer.sort((a, b) => a - b).join(" "));

DFS는 재귀 때문에 스택 오버플로우 위험성이 있어 아래처럼 BFS로도 풀어줄 수 있다.

// 다른 부분은 동일하게 하고 DFS 함수 대신 BFS 사용
function BFS(sx, sy) {
  let area = 1;
  const queue = [[sx, sy]];
  let idx = 0;

  while (idx < queue.length) {
    const [x, y] = queue[idx++];

    for (let [dx, dy] of move) {
      const nx = x + dx;
      const ny = y + dy;

      if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
      if (visited[nx][ny]) continue;
      if (board[nx][ny] === 1) continue;

      visited[nx][ny] = true;
      queue.push([nx, ny]);
      area++;
    }
  }

  return area;
}

[백준] 치즈

• 난이도 : 골드 4
• 문제 링크 : https://www.acmicpc.net/problem/2636

막힌 부분
1. 내부 구멍과 외부 구멍을 구분하는 방법
외부 구멍은 BFS로 바깥 영역을 돌면 모두 연결되어 있다. (내부 구멍은 치즈로 둘러싸여 있음.)
2. 외부 구멍과 맞닿은 영역만 제거하는 방법
외부 구멍과 맞닿은 영역을 바로바로 제거하면 안 되고 한 번에 제거해야 한다. 이를 위해 외부와 맞닿은 위치들을 모두 배열에 저장해두고 마지막에 한 번에 제거한다.
3. 외부 구멍은 한 번만 구하면 되는가?
치즈가 제거됨에 따라 내부 구멍이 외부 구멍과 연결될 수 있으므로 매시간마다 외부 구멍을 다시 구해줘야 한다. (이를 위해 방문 배열 매번 초기화 해야함)

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [M, N] = input[0].split(" ").map(Number);
const board = input.slice(1).map((r) => r.split(" ").map(Number));
const move = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];

function BFS(sx, sy) {
  const queue = [];
  const visited = Array.from({ length: M }, () => Array(N).fill(false));

  queue.push([sx, sy]);
  board[sx][sy] = 2;
  visited[sx][sy] = true;

  while (queue.length) {
    const [x, y] = queue.shift();

    for (let [dx, dy] of move) {
      const nx = x + dx;
      const ny = y + dy;

      if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
      if (visited[nx][ny]) continue;
      if (board[nx][ny] === 1) continue;

      visited[nx][ny] = true;
      board[nx][ny] = 2;
      queue.push([nx, ny]);
    }
  }
}

let lastCheese = 0;
let time = 0;

while (true) {
  // 치즈 개수 세기
  let currentCheese = 0;
  for (let i = 0; i < M; i++) {
    for (let j = 0; j < N; j++) {
      if (board[i][j] === 1) currentCheese++;
    }
  }

  // 더 이상 치즈 없으면 종료
  if (currentCheese === 0) break;

  lastCheese = currentCheese;

  BFS(0, 0); // 바깥 공기 표시

  const toMelt = []; // 공기와 맞닿은 치즈들

  for (let i = 0; i < M; i++) {
    for (let j = 0; j < N; j++) {
      if (board[i][j] === 1) {
        for (let [dx, dy] of move) {
          const nx = i + dx;
          const ny = j + dy;

          if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
          if (board[nx][ny] === 2) {
            toMelt.push([i, j]);
            break;
          }
        }
      }
    }
  }

  // 공기와 맞닿은 치즈들 한 번에 제거
  for (const [x, y] of toMelt) {
    board[x][y] = 2;
  }

  time++;
}

console.log(time);
console.log(lastCheese);

[백준] 탈출

• 난이도 : 골드 4
• 문제 링크 : https://www.acmicpc.net/problem/3055

. 비어있음
* 물 차있음 : 매 분 상하좌우로 확장. 돌, 비버로 이동 못 함.
X 돌 : 아무도 통과 못 함
D 비버 : 물 통과 못 함
S 고슴도치 : 매 분 상하좌우 중 하나로 이동. 돌, 물로 이동 못 함.

최소 시간을 구해야 하므로 BFS로 풀어야 한다.
먼저 고슴도치 위치를 찾아서 초기 시작 위치로 사용한다.
이후 매 분마다 상하좌우로 물을 한 칸씩 확장하고, 고슴도치를 상하좌우로 이동한다. (시간 +1)
고슴도치가 비버 굴에 도착하면 종료하고 시간을 반환한다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [R, C] = input[0].split(" ").map(Number);
const MAP = input.slice(1).map((r) => r.split(""));
const move = [
  [0, 1],
  [0, -1],
  [1, 0],
  [-1, 0],
];
let time = 0;
let sx = 0;
let sy = 0;

// 고슴도치 위치
for (let i = 0; i < R; i++) {
  for (let j = 0; j < C; j++) {
    if (MAP[i][j] === "S") {
      sx = i;
      sy = j;
      break;
    }
  }
}

let queue = [];
let isFinish = false;
const visited = Array.from({ length: R }, () => Array(C).fill(false));

queue.push([sx, sy, 0]);
MAP[sx][sy] = ".";
visited[sx][sy] = true;

while (queue.length && !isFinish) {
  const water = [];

  // 물 확장 위치 담아두기
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      if (MAP[i][j] === "*") {
        for (let [dx, dy] of move) {
          const nx = i + dx;
          const ny = j + dy;

          if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
          if (MAP[nx][ny] === ".") water.push([nx, ny]);
        }
      }
    }
  }

  // 물 확장
  for (let [wx, wy] of water) {
    MAP[wx][wy] = "*";
  }

  const temp_queue = [];

  while (queue.length) {
    // 고슴도치 위치
    const [x, y, t] = queue.shift();

    // 고슴도치 이동
    for (let [dx, dy] of move) {
      const nx = x + dx;
      const ny = y + dy;

      if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
      if (visited[nx][ny]) continue;
      if (MAP[nx][ny] === "X" || MAP[nx][ny] === "*") continue;

      // 비버 굴 도착한 경우 종료
      if (MAP[nx][ny] === "D") {
        time = t + 1;
        isFinish = true;
        break;
      }

      visited[nx][ny] = true;
      temp_queue.push([nx, ny, t + 1]);
    }
  }

  queue = [...temp_queue];
}

console.log(time > 0 ? time : "KAKTUS");

[백준] ABCDE

• 난이도 :골드 5
• 문제 링크 : https://www.acmicpc.net/problem/13023

그래프를 DFS로 탐색하며 depth가 4가 되면(5명이 연결되면) 1을 반환하고 안 되면 0을 반환하면 된다.
무방향 그래프이므로 그래프에 양방향을 모두 넣어주어야 하고, 백트래킹을 활용해 다른 경로에서 탐색한 노드를 재탐색할 수 있도록 해주어야 한다. 추가로 어떤 노드에서 depth가 4일지 모르기 때문에 시작 노드는 모든 노드가 되어야 한다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [N, M] = input[0].split(" ").map(Number);
const graph = Array.from({ length: N }, () => []);
const visited = Array.from({ length: N }, () => false);
let answer = 0;

for (let i = 1; i <= M; i++) {
  const [s, e] = input[i].split(" ").map(Number);
  graph[s].push(e);
  graph[e].push(s);
}

function DFS(node, depth) {
  if (depth === 4) {
    answer = 1;
    return;
  }

  visited[node] = true;

  for (let next of graph[node]) {
    if (!visited[next]) {
      DFS(next, depth + 1);
      if (answer) return;
    }
  }

  visited[node] = false;
}

for (let i = 0; i < N; i++) {
  DFS(i, 0);
  if (answer) break;
}

console.log(answer);

[백준] 키 순서

• 난이도 : 골드 4
• 문제 링크 : https://www.acmicpc.net/problem/2458

위와 다르게 키에 따라 방향이 정해지므로 방향 그래프이다.
자신의 키가 몇 번째인지 알 수 있는 학생의 수를 구해야 하는데, 자신의 키가 몇 번째일지 알기 위해서는 특정 학생보다 키가 큰 + 키가 작은 학생 수를 모두 구해서 더했을 때 전체 학생수 - 1과 같아야 한다.(본인 제외)

따라서 키가 큰 방향 / 키가 작은 방향으로 그래프를 각각 만들고, 모든 노드에 대해 DFS 탐색을 두 번 진행하여 합한 학생 수가 전체 학생 - 1인 수를 구해주었다.

(플로이도 와샬 알고리즘으로도 구할 수 있다.)

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [N, M] = input[0].split(" ").map(Number);
const tall_graph = Array.from({ length: N + 1 }, () => []);
const small_graph = Array.from({ length: N + 1 }, () => []);
const arr = Array(N + 1).fill(0);
let cnt = 0;

for (let i = 1; i <= M; i++) {
  const [s, e] = input[i].split(" ").map(Number);
  tall_graph[s].push(e);
  small_graph[e].push(s);
}

function DFS(node, depth, visited, graph) {
  visited[node] = true;

  for (let next of graph[node]) {
    if (!visited[next]) {
      cnt++;
      DFS(next, depth + 1, visited, graph);
    }
  }
}

for (let i = 1; i <= N; i++) {
  const tall_visited = Array.from({ length: N + 1 }, () => false);
  const small_visited = Array.from({ length: N + 1 }, () => false);

  DFS(i, 0, tall_visited, tall_graph);
  DFS(i, 0, small_visited, small_graph);

  arr[i] = cnt;
  cnt = 0;
}

console.log(arr.filter((c) => c === N - 1).length);

카운트를 전역 변수로 쓰는 대신 DFS에서 반환하도록 하고 배열로 모두 구하는 대신 정답이 되는 경우만 세도록 최적화할 수 있다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [N, M] = input[0].split(" ").map(Number);
const tall_graph = Array.from({ length: N + 1 }, () => []);
const small_graph = Array.from({ length: N + 1 }, () => []);
let answer = 0;

for (let i = 1; i <= M; i++) {
  const [s, e] = input[i].split(" ").map(Number);
  tall_graph[s].push(e);
  small_graph[e].push(s);
}

function DFS(node, depth, visited, graph) {
  visited[node] = true;
  let count = 0;

  for (let next of graph[node]) {
    if (!visited[next]) {
      count += 1 + DFS(next, depth + 1, visited, graph);
    }
  }

  return count;
}

for (let i = 1; i <= N; i++) {
  const tall_visited = Array.from({ length: N + 1 }, () => false);
  const small_visited = Array.from({ length: N + 1 }, () => false);

  const taller = DFS(i, 0, tall_visited, tall_graph);
  const smaller = DFS(i, 0, small_visited, small_graph);

  if (taller + smaller === N - 1) answer++;
}

console.log(answer);

[백준] 가장 가까운 공통 조상

• 난이도 : 골드 4
• 문제링크 : https://www.acmicpc.net/problem/3584

무방향 그래프지만 조상을 찾기 위해 부모 방향으로만 노드를 입력했다.
두 개의 노드 중 한 노드만 먼저 부모 노드를 모두 찾아 배열에 저장하고, 나머지 노드를 탐색할 때는 앞서 찾은 배열에 현재 노드가 포함될 경우 가장 가까운 공통 조상을 찾은 것이므로 바로 해당 노드를 반환하도록 했다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
let idx = 0;
const T = +input[idx++];
const answer = [];

function DFS(node, visited, parents, graph) {
  visited[node] = true;
  parents.push(node);

  for (let next of graph[node]) {
    if (!visited[next]) {
      DFS(next, visited, parents, graph);
    }
  }
}

function NEXT_DFS(node, visited, parents, graph) {
  visited[node] = true;

  if (parents.includes(node)) {
    return node;
  }

  for (let next of graph[node]) {
    if (!visited[next]) {
      const answer = NEXT_DFS(next, visited, parents, graph);
      if (answer) return answer;
    }
  }
}

for (let i = 0; i < T; i++) {
  const N = +input[idx++];
  const graph = Array.from({ length: N + 1 }, () => []);

  for (let j = 0; j < N - 1; j++) {
    const [s, e] = input[idx++].split(" ").map(Number);
    graph[e].push(s);
  }

  const [node1, node2] = input[idx++].split(" ").map(Number);
  const parents = [];

  DFS(
    node1,
    Array.from({ length: N + 1 }, () => false),
    parents,
    graph
  );

  const common_parent = NEXT_DFS(
    node2,
    Array.from({ length: N + 1 }, () => false),
    parents,
    graph
  );

  answer.push(common_parent);
}

console.log(answer.join("\n"));

트리여서 부모가 무조건 1개이므로 그래프로 관리할 필요가 없다.
또, DFS를 할 필요없이 부모 요소만 타고 올라가며 저장하면 된다.
추가로 배열에서 매번 includes로 확인하는 대신 Set을 활용하면 최적화할 수 있다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
let idx = 0;
const T = +input[idx++];
const answer = [];

for (let t = 0; t < T; t++) {
  const N = +input[idx++];

  const parent = Array(N + 1).fill(0);
  for (let i = 0; i < N - 1; i++) {
    const [p, c] = input[idx++].split(" ").map(Number);
    parent[c] = p;
  }

  const [a, b] = input[idx++].split(" ").map(Number);

  const ancestors = new Set();
  let cur = a;
  while (cur !== 0) {
    ancestors.add(cur);
    cur = parent[cur];
  }

  cur = b;
  while (!ancestors.has(cur)) {
    cur = parent[cur];
  }

  answer.push(cur);
}

console.log(answer.join("\n"));

[백준] 회사 문화 1

• 난이도 : 골드 4
• 문제 링크 : https://www.acmicpc.net/problem/14267

포인트

• 한 직원에 대해 직속 부하가 여러명일 수 있기 때문에 배열로 저장해야 한다.
• 칭찬을 할 때마다 DFS를 돌지 않고 칭찬을 먼저 입력해둔다음 한 번만 DFS를 돌면 된다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
let idx = 0;
const [N, M] = input[idx++].split(" ").map(Number);
const boss = input[idx++].split(" ").map(Number);
const tree = Array.from({ length: N + 1 }, () => []);
const praise = Array(N + 1).fill(0);

// 트리 구성
for (let i = 2; i <= N; i++) {
  tree[boss[i - 1]].push(i);
}

// 칭찬 입력
for (let i = 0; i < M; i++) {
  const [I, W] = input[idx++].split(" ").map(Number);
  praise[I] += W;
}

// DFS로 누적 전파
function dfs(node) {
  for (const child of tree[node]) {
    praise[child] += praise[node];
    dfs(child);
  }
}

dfs(1);

console.log(praise.slice(1).join(" "));

[백준] 미로 탈출하기

• 난이도 : 골드 3
• 문제 링크 : https://www.acmicpc.net/problem/17090

DFS로 모든 좌표를 방문하며 맵을 벗어나거나 탈출 가능한 좌표에 도달했을 때 탈출 가능 여부를 표시해준다. (한 좌표에서 탈출이 가능하다면 지나온 모든 좌표도 탈출이 가능하다는 뜻이므로 모두 탈출 가능하다고 표시해주고 다시 방문하지 않는다.)
반면에 이미 방문한 좌표에 다시 방문한 경우 탈출하지 못하고 같은 자리를 맴돌고 있는 것이므로 탈출 불가능하다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [N, M] = input[0].split(" ").map(Number);
const board = input.slice(1);
const visited = Array.from({ length: N }, () => Array(M).fill(false));
const possible = Array.from({ length: N }, () => Array(M).fill(false));
let answer = 0;

function DFS(x, y, path) {
  visited[x][y] = true;
  path.push([x, y]); // 방문한 경로 좌표 저장

  let [mx, my] = [x, y];

  // 명령어에 따른 다음 좌표 계산
  if (board[x][y] === "D") {
    mx += 1;
  } else if (board[x][y] === "U") {
    mx -= 1;
  } else if (board[x][y] === "L") {
    my -= 1;
  } else if (board[x][y] === "R") {
    my += 1;
  }

  // 탈출 가능한 경우 : 맵을 벗어나거나 탈출 가능한 좌표에 도달했을 때
  if (mx < 0 || my < 0 || mx >= N || my >= M || possible[mx][my]) {
    // 탈출 가능 체크
    for (let i = 0; i < path.length; i++) {
      const [px, py] = path[i];
      possible[px][py] = true;
    }
    return;
  }
  // 탈출 불가능한 경우 : 이미 방문한 곳에 다시 방문했을 때
  if (visited[mx][my]) return;

  DFS(mx, my, path);
}

// 방문하지 않은 모든 좌표에 대해 DFS
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (!visited[i][j]) DFS(i, j, []);
  }
}

// 탈출 가능한 좌표 개수 세기
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (possible[i][j]) answer++;
  }
}

console.log(answer);

방문 배열과 탈출 가능 배열을 각각 두지 말고 아래처럼 하나로 통합해서 관리하면 최적화가 가능하다. (방문 전, 방문 중, 탈출 가능, 탈출 불가능을 각각 다른 숫자로 표시)

const fs = require("fs");
const input = fs.readFileSync(0, "utf8").trim().split("\n");
const [N, M] = input[0].split(" ").map(Number);
const board = input.slice(1);

const state = Array.from({ length: N }, () => Array(M).fill(0));
// 0: unvisited, 1: visiting, 2: escape, 3: blocked

const dx = { U: -1, D: 1, L: 0, R: 0 };
const dy = { U: 0, D: 0, L: -1, R: 1 };

function dfs(x, y) {
  if (x < 0 || y < 0 || x >= N || y >= M) return 2;
  if (state[x][y] === 1) return 3; // cycle
  if (state[x][y] === 2 || state[x][y] === 3) return state[x][y];

  state[x][y] = 1; // visiting

  const nx = x + dx[board[x][y]];
  const ny = y + dy[board[x][y]];

  const result = dfs(nx, ny);
  state[x][y] = result;
  return result;
}

let answer = 0;

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (dfs(i, j) === 2) answer++;
  }
}

console.log(answer);