프로그래머스 - 43162번: 네트워크 [Java]

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] check = new boolean[n];
        for(int i = 0; i < n; i++) {
            if(check[i]) continue;
            DFS(n, computers, check, i);
            answer++;
        }
        return answer;
    }
    
    private void DFS(int n, int[][] computers, boolean[] check, int index) {
        check[index] = true;
        for(int i = 0; i < n; i++) {
            if(!check[i] && computers[index][i] == 1) {
                DFS(n, computers, check, i);
            }
        }
    }
}

2. 설명

    int answer = 0;
    boolean[] check = new boolean[n];
    for(int i = 0; i < n; i++) {
        if(check[i]) continue;
        DFS(n, computers, check, i);
        answer++;
    }

check는 노드의 방문 여부를 확인합니다. true라면 방문을 한 것이며 false라면 미방문 상태입니다.

반복문을 통해서 모든 노드에 접근을 진행하는데 이미 방문을 했던 노드라면 무시합니다. 미방문했다면 DFS 함수를 실행하여 노드와 이어진 노드를 탐색하여 방문을 진행합니다. 그리고 DFS할 때마다 answer를 1증가해줍니다.

private void DFS(int n, int[][] computers, boolean[] check, int index) {
    check[index] = true;
    for(int i = 0; i < n; i++) {
        if(!check[i] && computers[index][i] == 1) {
            DFS(n, computers, check, i);
        }
    }
}

DFS 함수가 실행되면 현재 노드에 방문했다는 것을 의미하기에 방문처리를 진행합니다. DFS 함수는 노드와 노드가 이어진 것과 미방문 여부를 확인 후 이어진 노드로 계속 진행합니다. index은 배열의 인덱스 값입니다. 

3. 정리

• 재귀와 반복문을 통해서 DFS 알고리즘을 쉽게 구현 가능하다.
• DFS/BFS에 대해서 겁먹지 말고 천천히 해보면 쉽게 해결된다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges