[프로그래머스] 43162번 - 네트워크 (JAVA)

출처: 프로그래머스 코딩테스트 연습

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

프로그래머스

---

문제

 

접근 방식

컴퓨터끼리 연결되어 있는 네트워크의 개수를 구하는 것에서 노드끼리 연결되어 있는 그래프, 즉 연결 그래프의 개수를 구하는 것과 비슷하다고 생각했다. 그래서 연결되어 있는 노드를 하나씩 끝까지 방문처리를 하면서 탐색하고, 다시 방문하지 않은 노드를 방문하는 과정을 반복하는 방법을 생각했다. 노드를 끝까지 탐색한다는 것에서 DFS를 떠올렸다. 

 

풀이

1. 방문하지 않은 컴퓨터를 탐색한다.
2. 방문한 컴퓨터부터 연결되어 있는 컴퓨터를 하나씩 탐색한다. 방문하면 방문 처리를 한다.
3. 더이상 연결된 컴퓨터가 없다면 처음 컴퓨터로 돌아간다.
4. 그 다음으로 방문하지 않은 컴퓨터부터 다시 탐색하고, 위 과정을 반복한다.

 

소스코드

class Solution {

    boolean[] visited;
    
    public int solution(int n, int[][] computers) {
        int answer = 0; // 네트워크의 개수
        
        visited = new boolean[n]; // 방문처리
        
        // 0번부터 n-1번까지 방문하지 않은 컴퓨터를 탐색
        for(int i=0; i<n; i++){
            if(!visited[i]){ 
                dfs(i, computers);
                answer ++; // 방문이 끝나면 네트워크 개수를 +1
            }
        }
        
        return answer;
    }
    
    public void dfs(int start, int[][] computers){
        // 현재 컴퓨터 방문처리
        visited[start] = true;
        
        // 현재 컴퓨터 start에 연결되어 있고, 방문하지 않았다면 해당 컴퓨터를 방문
        for(int i=0; i<computers.length; i++){
            if(computers[start][i] == 1 && !visited[i]){
                dfs(i, computers);
            }
        }
        
        
    }
}