[프로그래머스/Java] 네트워크(BFS/DFS 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 BFS/DFS 문제인 '네트워크'를 자바로 풀어보았다.

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

프로그래머스

 

 

 이 문제는 DFS를 이용해서 푸는 문제이다. BFS와 DFS에 대한 좀 더 자세한 설명이나 구현은 아래 글에서 볼 수 있다.

https://programming-diary-ina.tistory.com/30

[백준 1260번/C언어] DFS와 BFS, Queue로 풀이

 

 

 BFS나 DFS는 위 글처럼  Queue를 이용해서 구현하는 경우가 많은데, 이 문제의 경우 그보다 visited 배열로 방문 여부를 확인해 가면서 푸는 게 더 간단했다. 그래서 computer를 하나씩 순회하며, 방문하지 않았던 컴퓨터인 경우 하나의 네트워크의 시작으로 보고 answer, 즉 네트워크의 개수를 기록하는 변수에 하나를 더해준다. 그리고 그 computer에 연결된 모든 computer들에 방문 표시를 해주기 위해 dfs 함수를 호출하게 된다.

 dfs 함수에서는 일단 입력받은 현재 computer에 방문표시를 해준 다음 그 computer에 연결된 computer들을 순회하며 방문 표시를 해주면서, 다시 dfs 재귀 함수를 호출하여 연결된 computer들에 연결된 computer들까지 방문 표시를 해주게 된다. 

class Solution {
    public void dfs(int n, int[][] computers, int cur, boolean[] visited) {
        visited[cur] = true;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && computers[cur][i] == 1) {
                dfs(n, computers, i, visited);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                answer++;
                dfs(n, computers, i, visited);
            }
        }
        
        return answer;
    }
}