[DFS] 네트워크 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

[문제 간단 요약]

• n대의 컴퓨터가 있고, computers[i][j] = 1이면 i와 j가 직접 연결됨.
• 네트워크(연결 요소)의 개수를 구해야 한다.
• 즉, 연결된 노드들의 그룹 수를 찾는 문제.

[문제 해결 방안]

• 그래프의 연결 요소 개수를 찾는 전형적인 문제.
• 모든 노드에 대해 아직 방문하지 않은 경우 DFS/BFS 탐색을 수행.
• 탐색을 시작할 때마다 네트워크 수를 +1 증가.
• 인접 행렬이므로 각 노드마다 모든 노드를 확인 → 시간 복잡도는 O(n^2).

[문제 해결 코드 - Python]

def dfs(y, x, computers):
    global used
    used[y][x] = 1
    for dy in range(len(computers)):
        if computers[x][dy] == 1 and used[x][dy] == 0:
            used[x][dy] = 1
            dfs(x, dy, computers)

def solution(n, computers):
    global used
    answer = 0
    used = [[0] * n for _ in range(n)]
    for y in range(n):
        for x in range(n):
            if used[y][x] == 0 and computers[y][x] == 1:
                dfs(y, x, computers)
                answer += 1
    return answer

[문제 해결 코드 - JavaScript]

 

function solution(n, computers) {
    const used = Array(n).fill(false);
    const dfs = (start) => {
        const stack = [start];
        used[start] = true;
        while (stack.length) {
            const cur = stack.pop()
            for (let nxt = 0; nxt < n; nxt++) {
                if (cur === nxt) continue;
                if (computers[cur][nxt] === 1 && !used[nxt]) {
                    used[nxt] = true;
                    stack.push(nxt)
                }
            }
        }
    };
    
    let cnt = 0;
    for (let i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i);
            cnt++;
        }
    }
    return cnt;
}

1.  

[코드 개선점]

• 방문 배열 단순화 (n x n → n)
  기존에는 2차원 배열을 사용했지만, 실제로는 노드 방문 여부만 체크하면 되므로 1차원 배열로 충분
• 탐색 시작 조건 간소화
  모든 (y, x)를 이중 루프로 확인하는 대신, 노드 단위로 순회하며 방문 여부를 체크하는 방식이 직관적
• 인덱스 일관성 확보
  DFS 함수 파라미터를 (y, x) 대신 dfs(node) 형태로 작성하면 행·열 혼동을 줄일 수 있음
• 전역 변수 제거
  global used 대신 함수 내부 변수와 클로저를 사용하면 가독성과 재사용성이 좋아짐
• 반복 DFS 활용
  재귀 대신 스택을 활용한 반복 DFS로 구현하면 스택 오버플로우 위험을 줄이고, JavaScript 코드로 옮기기도 쉬움
• 복잡도 분석
  인접 행렬 탐색은 O(n^2)이지만, 개선된 방식은 불필요한 중복 체크를 줄여 더 효율적으로 동작