문제 설명

여러 친구관계가 주어졌을 때, A->B->C->D->E의 관계가 존재하는지를 탐색하는 문제이다.

하나의 친구에서 4개의 관계를 걸쳐 다른 친구로 통할 수 있는 경로가 있는가를 묻는 것

정답이 될 수 있는 경우의 수는 1-2-4-5-6, 3-2-4-5-6 이 있을 것이다.

이 경우의 수를 찾기 위해선, 노드를 타고가며 탐색을 해야한다.

DFS를 이용하여, 깊이를 증가시키며 연결된 노드를 타고가다 보면, 깊이가 4가 되는 구간을 찾을 수 있다.

깊이가 4가 되는 구간이 있다면, 그 즉시 DFS를 종료하고 1을 반환하면 된다. (더이상 DFS를 할 필요가 없다.)

반면, 끝까지 DFS를 했음에도, 깊이가 4가 되는 구간을 찾지 못했다면 0을 반환하면 된다.

이 문제에서 주의해야할 점은, 모든 점을 기준으로 DFS를 다 해야한다는 것이다.

코드풀이

초기코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const relationships = Array.from({ length: N }, () => []);

for (let n = 1; n <= M; n++) {
  let [a, b] = input[n].split(" ").map(Number);
  relationships[a].push(b);
  relationships[b].push(a);
}

// N명의 사람과 그들의 친구 관계(무방향 그래프)가 주어졌을 때,
// 4개의 다리(5명)로 연결된 연속적인 친구 관계(A-B-C-D-E)가 존재하는지 찾는 그래프 탐색 문제
console.log(relationships);

let visited = Array(N).fill(false);
function DFS(index, depth) {
  if (depth === M) {
    return 1;
  }

  visited[index] = true;

  for (const neighbor of relationships[index]) {
    if (!visited[neighbor]) {
      DFS(neighbor, depth + 1);
    }
  }

  visited[index] = false;
  return 0;
}

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

틀린부분 1. if (depth === M) { return 1; }

M이 아니라 4

틀린부분 2. let found = false; 필요

found여부를 체크하지 않음. 따라서 찾았어도, 남은 경우의 수를 다 찾아보게 됨

현재 DFS 함수는 return 0이나 return 1을 던지지만, 호출한 쪽에서 그 값을 받아서 처리하지 않고 있음

let found = false; // 1. 전역 상태로 관리

function DFS(index, depth) {
  if (found) return; // 2. 이미 찾았으면 바로 종료 (가지치기)
  
  if (depth === 4) { // 3. M이 아니라 4!
    found = true;
    return;
  }

  visited[index] = true;
  for (const neighbor of relationships[index]) {
    if (!visited[neighbor]) {
      DFS(neighbor, depth + 1);
      
      // 4. 재귀에서 돌아왔을 때 찾은 상태면 즉시 상위로 전달
      if (found) return; 
    }
  }
  visited[index] = false;
}

for (let i = 0; i < N; i++) {
  DFS(i, 0);
  if (found) break; // 5. 시작점 루프에서도 찾으면 즉시 중단
}

시간초과

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const relationships = Array.from({ length: N }, () => []);

for (let n = 1; n <= M; n++) {
  let [a, b] = input[n].split(" ").map(Number);
  relationships[a].push(b);
  relationships[b].push(a);
}

// N명의 사람과 그들의 친구 관계(무방향 그래프)가 주어졌을 때,
// 4개의 다리(5명)로 연결된 연속적인 친구 관계(A-B-C-D-E)가 존재하는지 찾는 그래프 탐색 문제
// console.log(relationships);

let visited = Array(N).fill(false);
let found = false;

function DFS(index, depth) {
  if (depth === N - 1) {
    found = true;
    return;
  }

  visited[index] = true;
  for (const neighbor of relationships[index]) {
    if (!visited[neighbor]) {
      DFS(neighbor, depth + 1);
      if (found) return; // 정답을 찾았다면 더 이상의 탐색 중단
    }
  }

  visited[index] = false; // 백트래킹: 다른 경로를 위해 방문 표시 해제
  return 0;
}

// 어떤 사람이 출발 점인지 모르니, 밖에서 모든 사람을 한 번씩 출발시켜야함
for (let i = 0; i < N; i++) {
  DFS(i, 0);
  if (found) break;
}

console.log(found ? 1 : 0);

if (depth === N - 1)

여기 때문! N이 몇 명이든 간에 depth가 4이면 된다. 즉 5명만 연속으로 연결되면 됨

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const relationships = Array.from({ length: N }, () => []);

for (let n = 1; n <= M; n++) {
  let [a, b] = input[n].split(" ").map(Number);
  relationships[a].push(b);
  relationships[b].push(a);
}

// N명의 사람과 그들의 친구 관계(무방향 그래프)가 주어졌을 때,
// 4개의 다리(5명)로 연결된 연속적인 친구 관계(A-B-C-D-E)가 존재하는지 찾는 그래프 탐색 문제
// console.log(relationships);

let visited = Array(N).fill(false);
let found = false;

function DFS(index, depth) {
  if (depth === 4) {
    found = true;
    return;
  }

  visited[index] = true;
  for (const neighbor of relationships[index]) {
    if (!visited[neighbor]) {
      DFS(neighbor, depth + 1);
      if (found) return; // 정답을 찾았다면 더 이상의 탐색 중단
    }
  }

  visited[index] = false; // 백트래킹: 다른 경로를 위해 방문 표시 해제
  return 0;
}

// 어떤 사람이 출발 점인지 모르니, 밖에서 모든 사람을 한 번씩 출발시켜야함
for (let i = 0; i < N; i++) {
  DFS(i, 0);
  if (found) break;
}

console.log(found ? 1 : 0);

고려할 점

DFS 내부에서 1,0리턴하는 방식

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const relationships = Array.from({ length: N }, () => []);

for (let n = 1; n <= M; n++) {
  let [a, b] = input[n].split(" ").map(Number);
  relationships[a].push(b);
  relationships[b].push(a);
}

// N명의 사람과 그들의 친구 관계(무방향 그래프)가 주어졌을 때,
// 4개의 다리(5명)로 연결된 연속적인 친구 관계(A-B-C-D-E)가 존재하는지 찾는 그래프 탐색 문제
console.log(relationships);

let found = false;
let visited = Array(N).fill(false);
function DFS(index, depth) {
  if (depth === 4) {
    return 1;
  }

  visited[index] = true;

  for (const neighbor of relationships[index]) {
    if (!visited[neighbor]) {
      if (DFS(neighbor, depth + 1) === 1) {
        return 1;
      }
    }
  }

  visited[index] = false;
  return 0;
}

이렇게 안에서 1, 0으로 처리하게 된다면, 다음과 같이 출력 처리 해야할 듯

let result = 0;
for (let i = 0; i < N; i++) {
  if (DFS(i, 0) === 1) {
    result = 1;
    break; // 여기서 루프 중단
  }
}
console.log(result);

코드 단순화 할 수 있는 부분

const relationships = input
  .slice(1, N + 1)
  .map((line) => line.split(" ").map(Number));

const relationships = [];

for (let n = 1; n <= N; n++) {
  // input[n]이 "1 2"라면, [1, 2]로 변환되어 저장됩니다.
  const friend = input[n].split(" ").map(Number);
  relationships.push(friend);
}