깊이/너비 우선 탐색(DFS/BFS)_네트워크

문제 설명💛

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.

예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때

컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.

 

따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

 

 

 

문제 핵심✔️

 

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때,

네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

 

https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java

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

참고해서 풀어보자.

이 문제는 DFS문제이다.

재귀호출을 이용해서 해결한다.

풀이 🔥

 

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0; //answer 0으로 초기화
        
        boolean[] check = new boolean[n]; //n개수만큼 boolean배열 만들고
        
        for(int i=0;i<n;i++){
            if(!check[i]){    //check[i]가 false인게 있다면, dfs호출하고 answer++해준다.
                dfs(computers, i, check);
                answer++;
            }
        }
        return answer;
    }
    boolean[] dfs(int[][] computers, int i, boolean[] check){
        check[i]=true;   //true로 변경하고 
        for(int j=0;j<computers.length;j++){
            if(i!=j && computers[i][j]==1 && check[j]==false){ //자기 자신이 아니며, false이며, 값이 1인것
                check=dfs(computers, j, check);  //재귀호출
            }
        }
        return check;
    }
}
  @Test
  public void 정답() {
    Assert.assertEquals(2, solution(3, new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
    Assert.assertEquals(1, solution(3, new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}}));
  }

@Test 코드 작성하는 법도 외워두자.