백준 13023 ABCDE

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let [n,m] = input.shift().split(" ").map(Number);
let arr = [];
for(let x of input){
    arr.push(x.split(" ").map(Number));
}

const solution = (n, arr) => {
  const graph = Array.from(Array(n), () => []);
  const check = new Array(n).fill(0);
  let flag = 0;
  for (let [a, b] of arr) {
    graph[a].push(b);
    graph[b].push(a);
  }

  const dfs = (cur, cnt) => {
    check[cur] = 1;
    if (flag) return;
    if (cnt === 4) {
      flag = 1;
    } else {
      for (let next of graph[cur]) {
        if (!check[next]) {
          dfs(next, cnt + 1);
        }
      }
    }
    check[cur] = 0;
  };

  for (let i = 0; i < n; i++) {
    dfs(i, 0);
  }
  return flag;
};


console.log(solution(n, arr));

• 서로 다른 노드끼리 연속적으로 4번 연결되면 조건을 만족한다.
• 그래서 dfs의 조건문이 저런식으로 나왔다.
• 인접행렬로 graph를 표현했을 때 시간초과가 나와서 인접리스트로 바꿨다.