[BOJ 13023] ABCDE

문제

ABCDE

https://www.acmicpc.net/problem/13023

 

 

풀이

설명

조건에 맞는 A, B, C, D, E가 존재하는지를 구하는 문제입니다.

 

DFS를 이용해 해결할 수 있습니다.

 

주어진 관계를 토대로 그래프를 구성한 후, 각 노드를 순회하며 dfs를 진행해 조건을 만족하는지 확인하면 됩니다.

 

예시 코드

function solution() {
  const [n, m] = input().split(" ").map(Number);
  const visited = Array(n).fill(false);
  const graph = Array.from(Array(n), () => []);
  let result = false;

  for (let i = 0; i < m; i++) {
    const [a, b] = input().split(" ").map(Number);
    graph[a].push(b);
    graph[b].push(a);
  }

  for (let i = 0; i < n; i++) {
    visited[i] = true;
    dfs(i, 0);
    visited[i] = false;
    if (result) return 1;
  }

  return 0;

  function dfs(node, depth) {
    if (depth === 4) {
      result = true;
      return;
    }

    for (const next of graph[node]) {
      if (visited[next]) continue;

      visited[next] = true;
      dfs(next, depth + 1);
      visited[next] = false;

      if (result) return;
    }
  }
}