그래프

경로탐색(인접행렬)

let edges = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 1],
  [2, 3],
  [2, 5],
  [3, 4],
  [4, 2],
  [4, 5],
];
let n = 5;

function solution(n, edges) {
  let answer = 0;
  let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
  let ch = Array.from({ length: n + 1 }, () => 0);

  // 인접행렬 생성
  for (let [a, b] of edges) {
    graph[a][b] = 1;
  }
  // 경로확인
  let path = [];
  function DFS(v) {
    if (v === n) {
      answer++;
      console.log(path);
    } else {
      for (let i = 1; i <= n; i++) {
        if (graph[v][i] === 1 && ch[i] === 0) {
          ch[i] = 1;
          path.push(i);
          DFS(i);
          ch[i] = 0;
          path.pop();
        }
      }
    }
  }
  // 시작점 체크
  ch[1] = 1;
  path.push(1);
  DFS(1);
  return answer;
}

경로탐색(인접리스트)

let edges = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 1],
  [2, 3],
  [2, 5],
  [3, 4],
  [4, 2],
  [4, 5],
];
let n = 5;

function solution(n, edges) {
  let answer = 0;
  let graph = Array.from(Array(n + 1), () => Array());
  let ch = Array.from({ length: n + 1 }, () => 0);

  // 인접리스트 생성
  for (let [a, b] of edges) {
    graph[a].push(b);
  }
  console.log(graph);
  // 경로확인
  let path = [];
  function DFS(v) {
    if (v === n) {
      answer++;
      console.log(path);
    } else {
      for (let nv of graph[v]) {
        if (ch[nv] === 0) {
          ch[nv] = 1;
          path.push(nv);
          DFS(nv);
          ch[nv] = 0;
          path.pop();
        }
      }
    }
  }
  // 시작점 체크
  ch[1] = 1;
  path.push(1);
  DFS(1);
  return answer;
}

동아리 개수

let n = 7;
let edges = [
  [1, 2],
  [2, 3],
  [1, 4],
  [1, 5],
];

function solution(n, edges) {
  let answer = 0;
  let graph = Array.from(Array(n + 1), () => Array());
  let ch = Array.from({ length: n + 1 }, () => 0);

  // 무방향 인접리스트 생성
  for (let [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
  function DFS(v) {
    for (let nv of graph[v]) {
      if (ch[nv] === 0) {
        ch[nv] = 1;
        DFS(nv);
      }
    }
  }
  for (let i = 1; i <= n; i++) {
    if (ch[i] === 0) {
      answer++;
      ch[i] = 1;
      DFS(1);
    }
  }
  return answer;
}

섬나라 아일랜드(DFS)

let board = [
  [1, 1, 0, 0, 0, 1, 0],
  [0, 1, 1, 0, 1, 1, 0],
  [0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 1, 1],
  [1, 1, 0, 1, 1, 0, 0],
  [1, 0, 0, 0, 1, 0, 0],
  [1, 0, 1, 0, 1, 0, 0],
];

function solution(board) {
  let answer = 0;
  let n = board.length;
  let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
  let dy = [0, 1, 1, 1, 0, -1, -1, -1];

  function DFS(x, y) {
    for (let k = 0; k < 8; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) {
        board[nx][ny] = 0;
        DFS(nx, ny);
      }
    }
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 1) {
        board[i][j] = 0;
        answer++;
        DFS(i, j);
      }
    }
  }
  return answer;
}

최대 선호 음식(BFS)

let nums = [[1], [2, 3], [3], [1, 2], [], [2, 1], [2, 3, 4], [3, 4]];
let d = 4;
let k = 3;

function solution(nums, d, k) {
  let answer = Number.MIN_SAFE_INTEGER,
    n = nums.length,
    pow = Array.from({ length: d + 1 }, () => 0),
    st = Array.from({ length: n }, () => 0);
  pow[1] = 1;
  // pow의 인덱스는 양념번호
  for (let i = 2; i <= d; i++) {
    pow[i] = pow[i - 1] * 2;
  }
  // 가중치값 완성
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < nums[i].length; j++) {
      st[i] += pow[nums[i][j]];
    }
  }

  function DFS(L, s, bit) {
    if (L === k) {
      let cnt = 0;
      for (let j = 0; j < n; j++) {
        if ((bit & st[j]) === st[j]) cnt++;
      }
      answer = Math.max(answer, cnt);
    } else {
      // i는 양념번호
      for (let i = s; i < d; i++) {
        DFS(L + 1, i + 1, bit + pow[i]);
      }
    }
  }
  DFS(0, 1, 0);
  return answer;
}

토마토

let board = [
  [0, 0, -1, 0, 0, 0],
  [0, 0, 1, 0, -1, 0],
  [0, 0, -1, 0, 0, 0],
  [0, 0, 0, 0, -1, 1],
];

function solution(board) {
  let answer = 0;
  let n = board.length;
  let m = board[0].length;
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];
  let dist = Array.from(Array(n), () => Array(m).fill(0));
  let que = [];
  function BFS() {
    while (que.length) {
      let cur = que.shift();
      for (let j = 0; j < 4; j++) {
        let nx = cur[0] + dx[j];
        let ny = cur[1] + dy[j];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] === 0) {
          board[nx][ny] = 1;
          dist[nx][ny] = dist[cur[0]][cur[1]] + 1;
          que.push([nx, ny]);
          answer = dist[nx][ny];
        }
      }
    }
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (board[i][j] === 1) {
        que.push([i, j]);
      }
    }
  }
  BFS();
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (board[i][j] === 0) {
        return -1;
      }
    }
  }

  return answer;
}

바둑대회

let nums = [
  [87, 84],
  [66, 78],
  [94, 94],
  [93, 87],
  [72, 92],
  [78, 63],
];

function solution(nums) {
  let answer = Number.MAX_SAFE_INTEGER;
  let ch = Array.from({ length: nums.length }, () => 0);
  function DFS(L, s, white) {
    if (L > nums.length / 2) return;
    if (L === nums.length / 2) {
      let black = 0;
      for (let i = 0; i < nums.length; i++) {
        if (ch[i] === 0) {
          black += nums[i][1];
        }
      }
      answer = Math.min(answer, Math.abs(white - black));
    } else {
      for (let i = s; i < nums.length; i++) {
        ch[i] = 1;
        DFS(L + 1, i + 1, white + nums[i][0]);
        ch[i] = 0;
      }
    }
  }
  DFS(0, 0, 0);
  return answer;
}