[ALGORITHM NINJA] 프로그래머스 DFS 2번 네트워크

NinjaJuunzzi·2021년 5월 11일
0

구현 아이디어

예를 들어 1번과 2번을 연결지으려고 한다면?

  • 둘 다 indexArray에 포함되어 있지 않다면 새로운 네트워크이므로 갯수추가.
  • 둘 중 하나라도 indexArray에 포함되어 있다면 네트워크를 확장하는 것이므로 갯수 추가하지 않는다.
  • 둘 다 indexArray에 포함되어 있다면 이미 네트워크에 포함되어 있는 경로이므로 함수를 리턴.

구현

function solution(n, computers) {
  let answer = 0;
  let indexArray = [];
  const func = (start, finish) => {
    // 중복체크
    const isStartInclude = indexArray.includes(start);
    const isFinishInclude = indexArray.includes(finish);
    
    
    if (isStartInclude && isFinishInclude) {
      // 둘다 중복되는 것이면 함수 돌릴필요없다. ( 이미 네트워크에 포함되어있으니깐 )
      return;
    }
    if (!isStartInclude && !isFinishInclude) {
      // 둘다 처음등장하는거면 네트워크 추가! 
      answer++;
    }
    
    
    // 방문자 체크를 해준다. 
    indexArray.push(start, finish);
    
    
    // 도착 인덱스에서 갈 수 있는 곳을 조사해서 호출한다.
    for (let check1 = 0; check1 < computers[finish].length; check1++) {
      
      // 자기자신이 아니면서 연결되어있는 곳은 호출한다.
      if (finish !== check1 && computers[finish][check1] === 1) {
        func(finish, check1);
      }
    }
  };
  
  
  
  for (let check = 0; check < computers.length; check++) {
    
    
    if (computers[check].filter((item) => item === 1).length === 1) {
      // 자기 자신 밖에 연결된게 없는 경우 네트워크 추가 !
      answer++;
    }
    
    
    for (let check1 = 0; check1 < computers[check].length; check1++) {
      
      // 자기자신이 아니면서 연결되어있는 경우 호출한다.
      if (check !== check1 && computers[check][check1] === 1) {
        func(check, check1);
      }
    }
  }
  return answer;
}

문제점

  • 자기자신만 연결되어 있는 경우의 처리 부분

다음은 자기 자신만 연결되어 있는 경우의 처리가 func 내부에서 되지 않아 solution메소드안에서 처리하는 모습이다.

 for (let check = 0; check < computers.length; check++) {
    if (computers[check].filter((item) => item === 1).length === 1) {
      // 자기 자신 밖에 연결된게 없는 경우 네트워크 추가 !
      answer++;
    }
    for (let check1 = 0; check1 < computers[check].length; check1++) {
      if (check !== check1 && computers[check][check1] === 1) {
        func(check, check1);
      }
    }
  }

지저분한 모습이다

  • indexArray.includes() 부분
    includes() 메소드의 경우 인자로 들어오는 값이 배열 안에 있는지를 점검한 후 참, 불참 값을 리턴한다.

배열을 한 번 순회해야하므로 복잡도 커질 것임

다른 사람의 코드

let arr;
let visitArr;

function solution(n, computers) {
    let ctr = 0;
    arr = computers;
    visitArr = new Array(n).fill(false);

    for(let i in arr) {
        ctr += dfs(i);
    }

    return ctr;
}

function dfs(i) {
    if(visitArr[i] == true) return 0;
    else visitArr[i] = true;

    for(let j in arr[i]) {
        if(arr[i][j] == 1)
            dfs(j);
    }

    return 1;
}

  • 자기 자신의 경로만 있는 경우 한 번도 등장하지 않았으므로 자연스럽게 처리

  • 굳이 나처럼 시작점과 도착점의 등장 여부를 판단하지 않아도 됨

solution(4, [
  [1, 1, 1, 0],
  [1, 1, 0, 1],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
]);

다음의 경우 2-0에서 한 번더 1을 리턴하지 않도록 하기위해 시작점을 검사했었음 (본인)
허나 이 사람의 코드처럼 들어가서 시작점의 모든 경로 다 포문으로 돌려놓으면 자연스럽게 처리됨

수정한 코드

  let answer = 0;
  const visited = [];
  const dfs = function (idx) {
    if (visited.includes(idx)) {
      return 0;
    } else {
      visited.push(idx);
      for (let check1 = 0; check1 < computers[idx].length; check1++) {
        if (computers[idx][check1] === 1) {
          dfs(check1);
        }
      }
      return 1;
    }
  };
  for (let check = 0; check < computers.length; check++) {
    answer += dfs(check);
  }
  return answer;
solution(4, [
  [1, 1, 1, 0],
  [1, 1, 0, 1],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
]);

을 실행시키는 경우

  • dfs(0)start -> dfs(0) return 0 -> dfs(1) -> dfs(0) return 0 -> dfs(1) return 0 -> dfs(3) -> dfs(1) return 0 -> dfs(3) return 0 -> dfs(2) -> dfs(0) return 0 -> dfs(2) return 0 -> return 1

  • dfs(1) -> dfs(0,1,3) 수행하지만 모두 중복 되어 리턴 0

  • dfs(2) -> dfs(0,2) 수행하지만 모두 중복되어 리턴 0

  • dfs(3) -> dfs(1,3) 수행하지만 모두 중복되어 리턴 0

profile
Frontend Ninja

0개의 댓글