프로그래머스 LEVEL 3(양과 늑대)

사용 언어 : javascript
해결 날짜 : 2023-05-13
해결 방법 :
- dfs를 활용해 문제 해결
  - 그래프 단방향 연결
  - 루트부터 dfs 수행
    - 현재 vertex가 0이면 sheep, 1이면 wolf 1 증가
    - 현재 움직일 수 있는 vertex와, 현재 vertex에서 움직일 수 있는 vertex 합치기
      - 하나씩 dfs 재귀
회고 :
- 처음에 new_movable에서 인덱스를 제거하는 과정에서 깊은 복사 대신 얕은 복사를 사용했다.
- 또한 노드를 왔다갔다 한다고 생각해 양방향 그래프로 문제를 해결하려 했으나 이미 방문했던 노드는 자식의 값만 있으면 방문하지 않아도 되므로 단방향 그래프로 문제를 해결했다.

코드

function solution(info, edges) {
  let answer = 0;

  const graph = Array.from({ length: info.length }, () => []);
  edges.forEach(([from, to]) => graph[from].push(to));

  const dfs = (current, sheep, wolf, movable) => {
    info[current] === 0 ? (sheep += 1) : (wolf += 1);

    answer = Math.max(answer, sheep);

    if (wolf >= sheep || sheep + wolf === info.length) {
      return;
    }

    const new_movable = [...movable, ...graph[current]];

    new_movable.forEach((m, i) => {
      dfs(m, sheep, wolf, [...new_movable.slice(0, i), ...new_movable.slice(i + 1)]);
    });
  };

  dfs(0, 0, 0, []);

  return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges