[프로그래머스_Lv3] 네트워크 ( by using JavaScript )

문제

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

 

How to Solve ?

[1] DFS

 

DFS 문제를 풀지 못하는 사람들도, DFS를 포함한 그래프 종류의 문제의 어려움 때문에 "재귀"로 동작한다던지, "스택"을 통해서도 구현이 가능하다던지 와 같은 이론을 빠삭하게 알고있지만 실제로 문제를 푸는 데에 있어서 어려움을 겪을 것이다. ( 나만 그럴수도,.?)

 

그래서 나는 DFS,BFS 문제만 보면 "나는 아직 이걸 풀 능력이 안돼" 라고 생각하고 항상 도망만 쳤는데, 정답도 참고하고 실제로 다시 코드를 작성하는 시간을 통해서 "사용법" 정도를 알아 낼 수 있었다.

 

DFS는 아까 이야기 했던 것처럼, 재귀 또는 스택을 기반으로 움직이며 "넓이"가 아닌 "깊이"를 목표로 움직인다.

 

문제의 목적으로 다시 돌아가서, 이 문제는 주어진 컴퓨터가 몇 개의 네트워크로 연결 되었는지 확인하는 문제이다. 즉, 한개의 컴퓨터를 시작으로 이어진 컴퓨터들을 DFS로 쭉 탐색하면서, 방문 처리를 하게 된다면

 

1) 1개로 연결 되어있을 때는, 다음 루프가 이어질 때 "모두 방문"을 했기 때문에 더 이상의 탐색은 필요 없어지고,

 

2) 2개 이상으로 연결이 되어있는 즉, 떨어져있다면 1번의 DFS만으로는 모두 방문이 안되어 추가적인 탐색이 요구될 것이다.

 

그런 점을 이용해 DFS를 처음으로 부르는 solution's for loop을 돌 때마다 count를 증가 시켜준다면, 몇 개의 네트워크가 모든 컴퓨터를 연결하는데 사용 되었는지 파악 할 수 있다.

function DFS(index, visited, computers) {
  visited[index] = true;

  for (let i = 0; i < computers.length; i++) {
    if ((computers[index][i] === 1) & !visited[i]) {
      DFS(i, visited, computers);
    }
  }
}

function solution(n, computers) {
  let answer = 0;
  const visited = [];

  for (const computer of computers) {
    visited.push(false);
  }

  for (let i = 0; i < computers.length; i++) {
    if (!visited[i]) {
      DFS(i, visited, computers);
      answer += 1;
    }
  }
  return answer;
}

let n = 3;
let computers = [
  [1, 1, 0],
  [1, 1, 0],
  [0, 0, 1],
];

console.log(solution(n, computers));