[Algorithm] 프로그래머스 - 네트워크

 

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

코딩테스트 연습 - 네트워크

 

위 문제는 양방향 그래프를 형성하고

전체 그래프를 순회하면서

몇개의 그룹이 존재하는지 판단하는 문제이다.

 

먼저 입력에 대한 그래프를 생성한다.

그래프를 작성하는 코드는 다음과 같다. 

(배열을 이용함)

 

배열의 의미 ( graph[ i ][ j ] = i번째 노드와 j번째 노드가 연결 되어있으면 1, 아니면 0 )

 

    int[][] graph;
    public int solution(int n, int[][] computers) {
        graph = new int[n][n];
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==j)  continue;
                if(computers[i][j] == 1){
                    graph[i][j] = 1;
                }
            }
        }
       //...
        return answer;
    }

computer[ i ][ j ]의 의미 : i 번째 노드가 j 번재 노드와 연결 되어있으면 1 아니면 0

자기 자신 (i==j) 은 무조건 1로 표현됨. 문제에 나와있다.

 

다음으로 만들어진 그래프(배열)을 1번노드 부터 n번 노드까지 모드 순회해 준다.

해당 문제를 해결하기 위해서는 2가지 방식이 존재한다.

1. DFS순회

2. BFS순회

 

아래 소스에서는 DFS를 이용하여 순회를 통해 그룹을 카운트 했다.

그룹 카운트를 하는 시점 -> 첫방문(루트) 방문이 끝나는 시점.

 

	// . 생략
	visited =  new boolean[n];
        for(int i=0; i<visited.length; i++){
            if(!visited[i]){
                dfs(i);
                answer++;
            }
        }
        //...

visited 배열의 의미.

해당 배열 n 번째 노드를 방문 했나 안했나 확인하는 배열.

방문 안했을 경우 해당 노드부터 dfs 수행.

dfs 모두 수행후 카운트 증가. (그룹 1개 형성)

 

dfs 코드

	public void dfs(int idx){
	  visited[idx] = true;
	    for(int i=0; i<visited.length; i++){
	      if(graph[idx][i] == 1 // (1)
          		&& !visited[i] ){ // (2)
	        dfs(i);
	      }
	    }
	}

먼저 해당노드를 방문처리.

다음 루프를 돌면서 현재 노드와 연결되어 있는지 확인한후 - > (1)

연결이 되어있다면 해당 노드가 방문 되어있는지 확인 -> (2)

두 조건 모두 만족시 해당노드로 다음 dfs 수행.

 

이렇게 순회 주면 한 노드 (시작노드) 에서

시작 노드와 연결된 모든 점을 순회한후 루프안에서 시작된 dfs가 종료되고

answer값을 1 증가 시키는 형태로 문제를 해결 할 수 있다. 

 

 

전체소스코드

 

import java.util.*;
class Solution {
    boolean[] visited;
    int answer = 0;
    int[][] graph;
    public int solution(int n, int[][] computers) {
        
        graph = new int[n][n];
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==j)  continue;
                if(computers[i][j] == 1){
                    graph[i][j] = 1;
                }
            }
        }
        
        visited =  new boolean[n];
        for(int i=0; i<visited.length; i++){
            if(!visited[i]){
                dfs(i);
                answer++;
            }
        }        
        return answer;
    }
    
    public void dfs(int idx){
        visited[idx] = true;
        for(int i=0; i<visited.length; i++){
            if(graph[idx][i] == 1 && !visited[i] ){
                dfs(i);
            }
        }
    }
}