[프로그래머스] 자바스크립트 '네트워크' 문제 풀이 (LV.3)

프로그래머스 자바스크립트 네트워크 문제 풀이

📖 들어가며

DFS 알고리즘을 사용하는 프로그래머스 '네트워크' 문제 풀이를 해보겠다.

❓ 문제 

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한 사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

입출력 예

n	computers	retrun
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #1

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

예제 #2

 

💡 풀이

DFS를 활용하는 문제다.

입력으로 2차원 배열을 받게 되는데, 받은 배열을 순회하면서 해당 인덱스를 방문을 했는지 안 했는지 체크를 안하게 되면 무한 루프에 빠지게 되기 때문에 방문 여부 체크가 정말 중요하다. 

그래서 먼저 방문 여부를 체크하기 위한 배열을 Array 메서드를 활용해 길이는 입력받은 길이와 동일하고 초기 값은 각각 false로 주었다.

그래서 해당 인덱스(컴퓨터)에 방문하지 않았다면 본격적으로 해당 인덱스를 넘겨주면서 dfs함수를 호출하게 된다.

dfs함수 안에서는 첫 번째로 방문을 했으니 해당 인덱스에 true 값을 주어서 방문을 했다고 체크를 하고,

다시 그 안에서 for문을 돌게 되는데 해당 컴퓨터와 연결되어 있고(value === 1) 방문하지 않았더라면 

다시 재귀로 뻗어 나가면서 방문했던 인덱스(컴퓨터)에 true 값을 주어 방문 체크를 해준다.

이제 dfs함수가 끝이 나면 초기 호출되었던 dfs함수로 돌아가서 answer의 값을 증가시켜줌으로써 네트워크 개수를 증가시켜 준다.

이 코드의 핵심은 방문 여부를 체크하며 if문을 통해 해당 컴퓨터와 연결 되어있는지, 방문을 했었는지를 재귀 함수로 뻗어나가면서 확인하고 answer의 값을 증가시켜 답을 리턴했다.

 

풀이 코드

function solution(n, computers) {
  let answer = 0;
  const length = computers.length;
  const visited = Array.from({ length: n }, () => false);

  function dfs(index) {
    visited[index] = true;

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

  for (let i = 0; i < length; i++) {
    if (!visited[i]) {
      dfs(i);
      answer++;
    }
  }

  return answer;
}

✔ 채점

채점 결과

 

🧐 후기

막상 풀었을 때는 어려운 문제는 아니었다. 아직 DFS문제인지 아닌지 어떤 식으로 해결해 나아가야 하는지 많이 부족한 것 같다. 문제를 이해할 때도 어려움이 있어서 꾸준히 여러 문제를 풀어보면서 DFS/BFS 알고리즘 문제에 능숙해져야겠다.