[프로그래머스 3단계] 연결된 정점드 with 자바스크립트(깊이 우선 탐색(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입니다.

입출력예시

코드

function solution(n, computers) {
    const adjList = {};
  for (let i = 0; i < n; i++) {
    adjList[i] = [];
  }
    //a=1 //b=2 // c=3
    for(let i=0; i< n; i++){
        for(let j=i+1; j <= n; j++){
            if(computers[i][i]===1 && computers[i][j]){
                adjList[i].push(j);
                adjList[j].push(i)
            }
        }
    }
   //방문한 버텍스 표시
  const visited = {}; // 0과 1에 방문했다면 {0=true, 1=true} 처럼 될것임  
  let count = 0; // 결과 출력을 위한 변수
  
  for (let vertex = 0; vertex < n; vertex++) {
    if (!visited[vertex]) { // 만약 방문한 적이 없는 정점이라면
      dfs(adjList, vertex, visited); // 순회(dfs)
      count++; // 카운트 증가
    }
  }
  return count; // 최종 결과
}

function dfs(adjList, vertex, visited) {
  visited[vertex] = true; // 먼저 해당 vertex를 체크한다. 
  for (let i = 0; i < adjList[vertex].length; i++) {
    if (!visited[adjList[vertex][i]]) {
      dfs(adjList, adjList[vertex][i], visited);
    } 
  }
}

 

해석

dfs를 사용하였다.

adj라는 객체에 0: [], 1: [] 식으로 0부터 시작하여 n-1개만큼 넣어준다.

이중 반복문으로 연결된 정점들을 배열안에 넣어준다. 빈객체를 만들어준다. 

visited에 키값이 true가 아니라면 dfs함수를 호출한다. 

//입출력예시 1번을 예를 들면

dfs안에서 adjList[0] = [1] 이 될것이다. 그럼 length의 길이도 1이기에 포문으로 들어간다.

if 조건에 충족함으로 adjList[vertext][i]의 값을 가지고 dfs를 다시호출한다.

 

한줄평

여러번 시행착오를 겪으며 풀게 되었다. 코드스테이츠 자료구조 코플릿에서 비슷한 문제를 풀었었는데, 아직 응용에 익숙하지가 못하다. 여러번 연습뿐이 답니다.

 

링크

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