[ 해결 과정 ]
1) n개수만큼 불린 배열을 만들고 false 로 초기화
2) n만큼 for문을 돌리다가, check[i] 값이 false 인게 있으면 깊이 우선 탐색을 하는 dfs 메서드를 호출하고,
네트워크 연결 개수를 ++ 해준다.
* dfs 인자 : computer[][] , i , check[]
3) 전달받은 피라미터인 check[i] 값을 true로 바꿔준다.
4) computer[]의 길이만큼 반복문을 돈다.
5) 만약 아래 조건이 모두 만족하면, 재귀호출을 한다.
- 자기 자신이 아니다. ( i != j )
- check 배열 i 위치의 값이 false 이며, (check[i] == false )
- computer 배열의 값이 1인 것 ( computer[i][j] == 0 )
6) 2번으로 돌아간다.
7) answer을 리턴한다.
[ 작성 코드 ]
public class network {
/**
- 컴퓨터 개수 n
- 연결에 대한 정보가 담긴 2차원 배열 (computer)
- 출력 : 네트워크 개수
**/
public static void main(String[] args) {
int n = 3;
int[][] computer1 = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
int[][] computer2 = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
solution(n, computer1);
solution(n, computer2);
}
public static int solution(int n, int[][] computers) {
int answer = 0;
boolean[] check = new boolean[computers.length];
for (boolean i : check) {
i = false;
}
for (int i = 0; i < computers.length; i++) {
if (check[i] == false) {
dfs(computers, i, check);
answer++;
}
}
return answer;
}
public static boolean[] dfs(int[][] computers, int n, boolean[] check) {
// n : 방문 노드, computer : 네트워크 배열, check : 방문했는지 확인하는 배열
check[n] = true;
for (int i = 0; i < computers.length; i++) {
if(n != i && computers[n][i] == 1 && check[i] == false){
// n != i : 방문 할 노드의 인덱스와 방문한 노드가 같지 않음
// computer[n][i] : 네트워크 배열에서 이제 방문할 배열 원소가 1인 경우
// check[i] == false : 아직 방문 하지 않은 경우
check = dfs(computers, i, check);
}
}
return check;
}
}