[프로그래머스] 네트워크

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

각 컴퓨터를 반복하면서 DFS 탐색을 하여 연결 관계를 확인하였습니다.

컴퓨터를 반복하던 중 이미 네트워크가 속한것을 확인한 경우, 건너뛰며 아직 속하지 않은 컴퓨터들을 탐색하며 네트워크 개수를 확인하였습니다.

2) 알고리즘

• DFS

3) 풀이 코드

사용 언어 - JavaScript

function solution(n, computers) {
  let answer = 0                                  // 정답 변수
  let visited = Array(n).fill(0)                  // 각 노드의 방문 여부를 저장
  let linked = Array(n).fill(0).map(() => [])     // 각 노드별 연결 관계 (2차원 배열)
  
  function dfs(start) {                 // DFS 탐색
    let stack = Array(1).fill(start)    // 초기 스택
    
    while (stack.length > 0) {          // 스택에 값이 남아있으면 반복
      let node = stack.pop()
      if (!visited[node]) {             // 해당 노드를 방문하지 않았으면, 방문 처리
        visited[node] = 1
        linked[node].forEach(v => {     // 연결된 노드들 추가
          stack.push(v)
        })
      }
    }
  }

  for (let i=0; i<n; i++) {             // 연결 관계 정리
    for (let j=i+1; j<n; j++) {
      if (computers[i][j] === 1) {
        linked[i].push(j)
        linked[j].push(i)
      }
    }
  }

  for (i=0; i<n; i++) {     // 노드들 반복하여
    if (!visited[i]) {      // 네트워크에 속하지 않은 노드이면
      dfs(i)
      answer++              // 네트워크 개수 추가
    }
  }


  return answer
}

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/43162?language=javascript 

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다