2020 카카오 인턴십 - 동굴 탐험

문제

코딩테스트 연습 - 동굴 탐험

구현

• 1차 구현 (정확성 통과, 효율성 실패)

  function solution(n, path, order) {    const nodes = Array.from({length: n}, () => new Node([], 0, false));    const start = nodes[0];    const locks = [];
      for (const p of path) {        nodes[p[0]].edges.push(p[1]);        nodes[p[1]].edges.push(p[0]);    }
      for (const o of order) {        nodes[o[1]].prior = o[0];    }
      if (start.prior !== 0) {        return false;    }
      start.visited = true;    start.edges.forEach((edgeNum) => visit(edgeNum, nodes, locks));
      if (nodes.some((node) => node.visited === false)) {        return false;    } else {        return true;    }}
  function visit(nodeNum, nodes, locks) {    const current = nodes[nodeNum];    const priorNode = nodes[current.prior];
      if (current.visited === true) {        return;    }
      if (priorNode.visited === false) {        locks.push(nodeNum);        return;    }
      current.visited = true;    const openNum = locks.find((lockNum) => nodes[lockNum].prior === nodeNum);    if (openNum) {        visit(openNum, nodes, locks);    }
      current.edges.forEach((edge) => visit(edge, nodes, locks));}
  class Node {    constructor(edges, prior, visited) {        this.edges = edges;        this.prior = prior;        this.visited = visited;    }}

  • 효율성 실패의 원인이 시간 초과도 있었지만 런타임 에러도 있었음. → 재귀 호출로 인한 stack overflow로 판단
• 2차 구현 (정확성 통과, 효율성 2/30 성공)

  function solution(n, path, order) {    const nodes = Array.from({length: n}, () => new Node([], 0, false));    const start = nodes[0];    const stack = [];    const locks = [];
      for (const p of path) {        nodes[p[0]].edges.push(p[1]);        nodes[p[1]].edges.push(p[0]);    }
      for (const o of order) {        nodes[o[1]].prior = o[0];    }
      if (start.prior !== 0) {        return false;    }
      start.visited = true;    start.edges.forEach((edge) => stack.push(edge));
      while (stack.length !== 0) {        const nodeNum = stack.pop();        const availables = visit(nodeNum, nodes, locks);        availables.forEach((availNum) => stack.push(availNum));    }
      if (nodes.some((node) => node.visited === false)) {        return false;    } else {        return true;    }}
  function visit(nodeNum, nodes, locks) {    const current = nodes[nodeNum];    const priorNode = nodes[current.prior];
      if (current.visited === true) {        return [];    }
      if (priorNode.visited === false) {        locks.push(nodeNum);        return [];    }
      current.visited = true;
      const openNum = locks.find((lockNum) => nodes[lockNum].prior === nodeNum);    if (openNum) {        return [...current.edges, openNum];    }    return [...current.edges];}
  class Node {    constructor(edges, prior, visited) {        this.edges = edges;        this.prior = prior;        this.visited = visited;    }}

  • visit 함수를 재귀호출하지 않고, 방문할 노드 목록을 stack으로 관리한 뒤 visit 함수에서는 방문할 노드 리스트를 리턴하게끔 수정함.

  • 효율성 테스트의 2개 테스트 케이스에 대해서만 통과했는데, 나머지는 모두 시간초과로 인한 에러였음.

• 최종 (정확성, 효율성 모두 통과)

  function solution(n, path, order) {    const nodes = Array.from({length: n}, () => new Node([], 0, false, 0));    const start = nodes[0];    const stack = [];
      for (const p of path) {        nodes[p[0]].edges.push(p[1]);        nodes[p[1]].edges.push(p[0]);    }
      for (const o of order) {        nodes[o[1]].prior = o[0];    }
      if (start.prior !== 0) {        return false;    }
      start.visited = true;    start.edges.forEach((edge) => stack.push(edge));
      while (stack.length !== 0) {        const node = stack.pop();        const availables = visit(node, nodes);        availables.forEach((availNum) => stack.push(availNum));    }
      if (nodes.some((node) => node.visited === false)) {        return false;    } else {        return true;    }}
  function visit(node, nodes) {    const current = nodes[node];    const priorNode = nodes[current.prior];
      if (current.visited === true) {        return [];    }
      if (priorNode.visited === false) {        priorNode.next = node;        return [];    }
      current.visited = true;
      if (current.next) {        return [...current.edges, current.next];    }    return [...current.edges];}
  class Node {    constructor(edges, prior, visited, next) {        this.edges = edges;        this.prior = prior;        this.visited = visited;        this.next = next;    }}

  • locks 배열에 노드 목록을 담아두고, 이번 방문을 통해 방문할 수 있게 된 노드를배열에서 find 함수로 찾는 과정이 추가적인 시간 복잡도를 발생시켰음 ... (이걸찾는데 꽤나 해멨다.)

어려웠던 점

1. 문제 자체의 난이도가 꽤 있었던 문제였다.

2. 그림은 트리 형태로 주어져 있지만 입력 값에서 트리 형태로 만드는 것은 어려웠다 . 결국 그래프 형태에서 dfs를 사용해 해결했는데, 처음에 트리라고 생각하니 문제해결 법을 고민하는데 오래걸렸다.

3. 효율성 문제를 고려하지 않았다가 제출하고 나서 효율성이 모두 실패하자 효율성을고려해야 함을 깨달았다. 그리고 효율성 문제를 파악하는 것이 어려웠다. (어디에서 시간 복잡도가 증가하는지 찾기)

배운 점

• VSCode + Node + Jest 환경으로 디버깅 환경을 구축했다.

  • F5 키만 누르면 VSCode의 현재 열려있는 파일의 상위 디렉토리를 Jest로 디버깅모드로 실행시킬 수 있다.

  • .vscode/launch.json 을 다뤘다.

  NodeJS, Jest, VSCode debugging

• 효율성 문제가 발생하면 "JS라서 그런가" 하는 생각부터 들었는데, 결국 문제는 내가 짠 코드에 있었다. 효율성 문제를 고려해야한다는 것을 배웠다.

참고자료

2020 카카오 인턴십 for Tech developers 문제해설

[ 프로그래머스 - 동굴 탐험 ] 해설 및 코드

[프로그래머스] 동굴 탐험