[CodeKata] 프로그래머스 : 5.3(월), 네트워크

🥋 Oooth More!! (Level 3)

 

🧮 풀이

function solution(n, computers) {
  let answer = 0;
  let nodes = Array.from({ length: n }, (_,i) => i);
  let queue = [];
  while (nodes.length > 0) {
    if (queue.length === 0) {
      answer++;
      queue.push(nodes.shift());
    }
    else {
      const now = queue.shift();
      nodes.forEach(node => {
        if (computers[now][node] === 1) {
          queue.push(node);
          nodes = nodes.filter(e => e !== node);
        }
      })
    }
  }
  return answer;
}

1. BFS(+queue) 를 활용한 풀이다. queue에 노드를 넣고, queue가 빌 때까지 인접 노드들을 계속 탐색하는 방법이다.
2. nodes는 n(개수)을 인덱스들로 만든 배열, queue는 이 노드들을 탐색중에 임시저장할 저장소, answer는 네트워크 카운트 수다.
3. nodes가 빌 때까지 while 반복문을 순회한다. queue가 빈 경우(새로운 네트워크 탐색), 있는 경우(인접 노드 검색) 2가지가 있다.
4. 새로운 네트워크 탐색은, answer 개수를 먼저 1을 더해준다. 그리고, nodes의 노드 하나를 queue에 담아준다.
5. 인접 노드 검색은, queue의 노드 하나를 꺼내온다. 다음, computers에서 이 노드와 연결된(1) 모든 노드를 queue에 담고 nodes에서 지운다. 이렇게 되면, 해당 else문이 종료된 다음에도 queue가 비어있지 않으므로 이 로직이 재실행된다. (인접노드 기준으로)
6. 최종적으로, answer를 반환하면 된다.

 

🖇 리뷰

1) BFS 개선방법

위 풀이가 소요시간이 좀 더 짧았다. 아마, visitedNode를 true/false로 토글링하기 때문에, 배열가공이 최소화되지 않았나 싶다.

 

2) DFS 다른방법

이 문제는, DFS나 BFS 둘 중 아무 방법이나 사용해도 무방하다. 결국, 모든 노드를 탐색하기만 하면 되기 때문이다.

function solution(n, computers) {
    var answer = 0;
    
    const check = [];
    for(const computer of computers){
        check.push(false);
    }
        
    function DFS(index){
        check[index] = true;
        
        for(let i = 0; i< computers.length; i++ ){
            if(computers[index][i] === 1 && !check[i]){
                DFS(i);
            }
        }
    }
    
    for(let  i = 0;  i < computers.length; i++ ){
        if(!check[i]){
            DFS(i);
            answer+=1;
        }
    }
        
    return answer;
}

check는 visitedNode와 같은 역할이다. (마찬가지로 true/false 토글링)

DFS() 함수는 인덱스를 인자로 받아, check의 현재 인덱스를 true로 변환하고 computers에서 다음 이동할 수 있는 인덱스를 재귀한다.

이를, for문을 통해 0부터 순회하며 현재 check가 false인 (방문하지 않은) 노드에서 DFS() 함수를 실행하면 된다.