9466 텀 프로젝트 (Node.js)

패스트캠퍼스 나동빈 강사님 강의를 보면서 알고리즘을 학습하고 있습니다.

제가 유독 dfs, bfs, 이쪽에 약한 거 같아서,, 한번 포스팅으로 정리하면서 이해해 보려고 합니다.

참고했던 포스팅으로는 https://forward-gradually.tistory.com/61 이 있습니다.

 

초기에 혼자 썼던 코드,, 예제에서 주어진 케이스는 통과했는데, 실제 테스트에선 실패했습니다.

반례를 찾던 중 위 포스팅하신 분의 반례 케이스를 테스트 해보니 다 틀리더군요...

4
3
2 3 3
5
2 3 4 5 4
4
2 3 4 2
5
1 1 1 1 1


//답
2
3
1
4

 

const fs = require('fs');
const input = fs
  .readFileSync(__dirname + '/input.txt')
  .toString()
  .split('\n');
let visited = [];
const testCase = +input[0];
let favorite = [];
let selected = [];
let count = 0;
for (let t = 0; t < testCase; t++) {
  const memberCnt = +input[1 + 2 * t];
  favorite = input[2 + 2 * t].split(' ').map((e) => e - 1);
  count = 0;
  visited = new Array(memberCnt).fill(false);
  for (let i = 0; i < memberCnt; i++) {
    if (!visited[i]) {
      selected = [i];
      visited[i] = true;
      dfs(favorite[i]);
    }
  }
  console.log(count);
}

function dfs(like) {
  if (!visited[like]) {
    visited[like] = true;
    const favOfLike = favorite[like];
    if (favOfLike === like) {
      count++;
    } else if (visited[favOfLike]) {
      const targetIndex = selected.findIndex((e) => e === favOfLike);
      if (targetIndex !== -1) {
        count += selected.length - targetIndex;
      }
    } else {
      selected.push(like);
      dfs(favOfLike);
    }
  }
}

 

생각했던 로직

1. 학생들은 1번 부터 n까지 번호가 주어지기 때문에, 각각의 case에서  Map을 돌릴 때,  1을 뺀 값을 통해 새로운 배열을 만듭니다.  ( favortie 배열)

2. 이후 중복 작업을 제거하기 위해서 visited 배열을 만들었고, 현재 dfs에서 선택된 녀석들을 담을 selected 배열을 만들었습니다.

3. 새로운 dfs가 실행될 떄마다 selected를 초기화 시켜줬고, 각각의 케이스마다 visited와 favorite 배열을 초기화 시켰습니다.

 

위 코드로 해당 케이스 테스트 시  1 1 2 0 이 나옵니다..

1차 보완

일단  dfs함수가 잘못 된 부분이 많았네요..그리고 for 문 안에서 이미 좋아했떤 애를 좋아하는 경우에 대한 경우가 없었네요..
위의 케이스에 대해선 통과 했는데 여전히 틀린 코드 뭐가 문젤까요..

let visited = [];
const testCase = +input[0];
let favorite = [];
let selected = [];
let count = 0;
for (let t = 0; t < testCase; t++) {
  const memberCnt = +input[1 + 2 * t];
  // 케이스마다 좋아하는 배열 초기화
  favorite = input[2 + 2 * t].split(' ').map((e) => e - 1);
  // 조 못이룬 사람 수
  count = 0;
  // 확인 한 경우
  visited = new Array(memberCnt).fill(false);

  for (let i = 0; i < memberCnt; i++) {
    //아직 확인 안 한 사람중에
    if (!visited[i]) {
      // 현재 순회중인 대상
      selected = [i];
      visited[i] = true;
      const like = favorite[i];
      if (like === i) {
        // 혼자 하는 놈
      } else if (visited[like]) {
        // 이미 탐색이 끝난 애(조를 이루거나 조가 이루어 질 수 없는 애랑 하고 싶어하면 실패)
        count++;
      } else {
        // 나머진 탐색
        dfs(like);
      }
    }
  }
  console.log(count);
}

function dfs(like) {
  visited[like] = true;
  const favOfLike = favorite[like];
  if (favOfLike === like) {
    // 혼자 하고 싶어하면 순회중인 나머진 조 못 이룸
    count += selected.length;
  } else if (visited[favOfLike]) {
    // 이미 방문했던 애를 좋아한다면
    const targetIndex = selected.findIndex((e) => e === favOfLike);
    if (targetIndex === -1) {
      // 순회 중이지 않다면
      count += selected.length;
    } else {
      // 만약 대상이 현재 순회중인 애 라면
      count += targetIndex;
    }
  } else {
    // 순회 대상에 추가하고 새로운 애를 통해 순회
    selected.push(like);
    dfs(favOfLike);
  }
}

 

2차보완

let visited = [];
const testCase = +input[0];
let favorite = [];
let selected = [];
let count = 0;
for (let t = 0; t < testCase; t++) {
  const memberCnt = +input[1 + 2 * t];
  favorite = input[2 + 2 * t].split(' ').map((e) => e - 1);
  count = 0;
  visited = new Array(memberCnt).fill(false);

  for (let i = 0; i < memberCnt; i++) {
    if (!visited[i]) {
      visited[i] = true;
      const like = favorite[i];
      if (like === i) {
      } else if (visited[like]) {
        count++;
      } else {
        selected = [i];
        dfs(like);
      }
    }
  }
  console.log(count);
}

function dfs(like) {
  visited[like] = true;
  const favOfLike = favorite[like];
  if (favOfLike === like) {
    count += selected.length;
  } else if (visited[favOfLike]) {
    const targetIndex = selected.findIndex((e) => e === favOfLike);
    if (targetIndex === -1) {
    //수정
      count += selected.length + 1;
    } else {
      count += targetIndex;
    }
  } else {
    selected.push(like);
    dfs(favOfLike);
  }
}

순환중이지 않다면의 조건을 잘못 걸었다.. selected.length+1 왜냐면   순회대상은 아직 selected배열에 안 넣었으니깐..

성능도 향상이 많이 됐다. 앞에 처음 맞춘 코드는 강사님 코드입니다.

성능차이가 나는건,  강사님의 경우 방문과 완료 두 가지 배열을 사용하고,  성공적으로 팀을 이룬 ( 사이클이 생성된 경우) 경우에 result배열에 넣는 방식을 사용하였습니다. 즉 3개의 배열에 값을 수정하면서 최종결과가 도출됐기 떄문에, 시간도 1.5배 정도 걸린 것이라 저는 생각했습니다..

 

DFS랑 그래프에 유독 약했는데, 혼자 풀었던 게 성능이 좋아서 기분이 좋네요,,

const fs = require('fs');
const input = fs
  .readFileSync(__dirname + '/input.txt')
  .toString()
  .split('\n');

let testCases = +input[0];
let line = 1;
while (testCases--) {
  let n = +input[line];
  let graph = [0, ...input[line + 1].split(' ').map(Number)];
  let visited = new Array(n + 1).fill(false);
  let finished = new Array(n + 1).fill(false);
  let result = [];
  for (let x = 1; x <= n; x++) {
    if (!visited[x]) dfs(x, graph, visited, finished, result);
  }
  line += 2;
  console.log(n - result.length);
}
function dfs(x, graph, visited, finished, result) {
  visited[x] = true;
  let y = graph[x];
  if (!visited[y]) {
    dfs(y, graph, visited, finished, result);
  } else if (!finished[y]) {
    while (y !== x) {
      result.push(y);
      y = graph[y];
    }
    result.push(x);
  }
  finished[x] = true;
}