https://programmers.co.kr/learn/courses/30/lessons/42898
직, 간접적으로 연결된 컴퓨터들을 하나의 네트워크라고 본다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때,
네트워크의 개수를 구해야한다.
입력 : n
3, computers
[[1, 1, 0], [1, 1, 0], [0, 0, 1]]
1번과 2번 네트워크는 연결되어있고,
3번 네트워크는 어느 네트워크와도 연결이 되어있지 않기 때문에 총 네트워크의 갯수는 2개이다.
입력 : n
3, computers
[[1, 1, 0], [1, 1, 1], [0, 1, 1]]
1번과 2번은 직접적으로, 2번과 3번은 직접적으로 연결되어있고,
1번과 3번은 직접적으로 연결되어있지 않지만 2번을 통해 간접적으로 연결되어있기 때문에,
총 네트워크의 갯수는 1개이다.
입력 : n
3, computers
[[1, 1, 0], [1, 1, 0], [0, 0, 1]]
1) n 갯수만큼 boolean 배열을 만들고 모든 요소를 false로 초기화한다.
2) n만큼 for문을 돌다가, check[i]값이 false인게 있으면 깊이우선탐색을 하는 dfs 메소드를 호출하고, answer++을 해준다.
- dfs 메소드의 전달 인자로는 computer[][], i, check[]를 넘겨준다.
— dfs() —
3) 전달받은 파라미터인 check[i]값을 true로 바꿔준다.
4) computer[]의 길이(3)만큼 반복문을 돈다. (j)
5) 만약 아래 조건을 모두 만족하면, 재귀호출을 한다.
- 자기 자신이 아니며 (i ≠ j)
- check 배열 i 위치의 값이 false이며 (check[i] == false)
- computer 배열의 값이 1인 것 (computer[i][j] == 0)
6) 2번으로 돌아간다.
7) answer을 리턴한다.
public class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
boolean[] check = new boolean[n]; // n 갯수만큼 boolean 배열을 만들고 모든 요소를 false로 초기화
for (int i = 0; i < n; i++) {
if (!check[i]) {
dfs(computers, i, check);
answer++;
}
}
return answer;
}
boolean[] dfs(int[][] computers, int i, boolean[] check) {
check[i] = true;
for (int j = 0; j < computers.length; j++) {
if (i != j && computers[i][j] == 1 && check[j] == false) {
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}}));
}
}