프로그래머스 - 네트워크

문제 설명

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

ncomputersreturn

3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

 

DFS/BFS 문제였다. 

나는 DFS 로 풀이를 해보았다. 

최근 올린 풀이들은 C++ 로 진행했지만 Java 언어로 푸는 연습도 할겸 이번에는 java로 풀이해보았다.

 

일단 코드를 보자.

 

import java.util.*;

class Solution {    
    
    static int[]visited;
    static int cn=0;
    public int dfs(int node , int [][]computers ){
        visited[node]=1;

        for(int i=0;i<computers.length;i++){
                  if(visited[i]==0 && computers[node][i] ==1){
                      dfs(i ,computers );
                      cn++;
                  }
            }   
        
        return cn;
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        Vector<Integer> v = new Vector<Integer>();
        int result=0;
        visited = new int [n];
        for(int i=0;i<computers.length; i++){
            if(visited[i] ==0){
                result=dfs(i,computers);
                v.add(result);
                cn =0;
            }
        }
        answer = v.size();
        return answer;
    }
}

 

이번 네트워크 문제처럼 그래프가 나오고 선으로 연결 된 자료를 주는 문제들은

이런 풀이와 비슷한 느낌을 가진다.

한번 방문한 곳은 다시 방문할 필요가 없으므로 visited 배열은 선언해줬다.

computers 는 2차원 배열이지만 문제를 잘 읽어보면 visited 배열은 A , B ,C 즉 각 노드들의 방문여부만 체크하면 되기 때문에 1차원 배열로 선언해도 문제없다.

 

먼저 solution 에서 for 문을 통해서 방문하지 않은 노드들에 대해서 dfs 를 실행한다.

dfs의 node 라는 지금 탐색하려는 기준이 되는 노드를 의마한다.

예를들어 A - B - C 로 연결된 네트워크라면 A와 B 의 연결을 의미하는 원소 1 을 computers 라는 배열에서 찾아냈다면

이 다음에는 B에서 다른곳으로 연결 될 노드가 있는지 탐색을 해야한다.

 

그래서 dfs 의 for문안에 if(visited[i]==0 && computers[node][i] ==1) 이 코드를 통해 해당 동작을 한다.

computers의 x 좌표가 node 로 들어오면 B 노드와 연결 된 노드가 있는지 쭉 탐색하게 된다. 

이 과정에서 A도 탐색이 될텐데 A는 이미 방문을 했고 visited 에서 체크가 되었기때문에 무시하고 그 다음에 나오게 되는 C가 선택되는것이다. 

그리고 그때의 i 값이 dfs 의 node 값으로 들어가게 되면서 연결된 모든 노드를 순서대로 찾아내게 된다.

한번 dfs를 실행할때마다 노드 하나를 연결한다는 의미이므로 cn 을 증가시킨다. (사실 이 cn의 값은 의미가 없다. 다른 좋은 방법이 있을것이다.)

 

이 cn을 하나의 dfs가 끝날때 vector 에 넣어주면

모든 동작이 끝났을때 이 vector의 크기가 네트워크의 갯수가 되는 것이다.