43162. 네트워크

🔻 네트워크

프로그래머스 lv3_네트워크

👀
DFS를 적용한 첫 풀이여서 기록차 작성! 프로그래머스 AI 가 엄청 어려운 ,, dfs만 추천해줘서 다 건너뛰다 마주한 적당한 난이도의 dfs,, dfs의 왕이 되는 그 날까지 🥹

[👩🏻‍💻내 코드]

function solution(n, computers) {
    let visited = [];
    let answer = 0;
    for (let i = 0; i<n; i++) {
        if (!visited[i]) {
            // 탐색
            dfs(i, visited, computers);
            answer += 1;
        }
    }
    return answer;
}

function dfs(node, visited, computers) {
    visited[node] = true;
    for (let j = 0; j < computers.length; j++) {
        if (computers[node][j] === 1 && !visited[j]) {
            dfs(j, visited, computers);
        }
    }
}

✅ DFS

DFS는 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법으로 stack 자료구조를 활용한다.

1️⃣ 시작 노드를 스택에 넣어두고 방문 처리한다
2️⃣ 스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다.
-> 있다면, 방문하고 스택에 삽입 후 방문 처리
-> 없다면 현재 노드를 스택에서 추출
3️⃣ 2번 과정을 반복할 수 없을 때까지 반복

이 문제의 경우 stack을 visited 변수로 두고 구현하였다.
각 Node를 확인하며 연결 되어있고, visited되지 않았다면 해당 노드를 탐색한다 !
주석을 통해 확인해보자

function solution(n, computers) {
  // 연결을 관리할 stack
    let visited = [];
    let answer = 0;
  // 각 컴퓨터 탐색
    for (let i = 0; i<n; i++) {
      // 방문하지 않았다면 탐색하기 !
        if (!visited[i]) {
            dfs(i, visited, computers);
            answer += 1;
        }
    }
    return answer;
}

// Node : 컴퓨터 번호
// visited : 각 컴퓨터에 접근했는지를 index를 통해 접근 !
function dfs(node, visited, computers) {
  // 해당 node를 (컴퓨터를) 방문 처리
    visited[node] = true;
  // 해당 컴퓨터의(computers의 각 요소) 배열 값들을 보며 연결 여부 확인
    for (let j = 0; j < computers.length; j++) {
      // 연결 되어있고, 방문한 적 없는 경우
        if (computers[node][j] === 1 && !visited[j]) {
          // 탐색 !
            dfs(j, visited, computers);
        }
    }
}