[프로그래머스] 네트워크연결

문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.
입출력 예

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

해결전략

1. 각 컴퓨터의 연결 상태를 기록하는 boolean[] 을 만든다.
2. 연결이 되어 있지 않으면 종료되는 반복문을 돌린다.
3. 각각의 컴퓨터는 1번부터 n번까지 쭉 나열되어 있고, 트리 노드처럼 계층이 나뉘어져 있는게 아닌데 DFS 를 쓸 수 있을까? (DFS)
4. 생각해보니 단순히 i++ 해서 돌면 (1,2) (1,3) 이 연결되어있는데 (2,3) 은 끊어져 있을 경우 판별하는 게 불가능 할 것 같다.
5. DFS 에서 백트래킹처럼 이전 노드로 돌아가서 다음 노드를 탐색하는 것이 필요할 것 같다.
6. computers[i][2] = 1 이면 진행, computer[i][2] = 0 이면 상태를 false 로 만들고 부모로 돌아가기
7. 배열, i, 상태배열 을 함수의 인자로 전달해서 재귀
8. dfs 에 방문하면, check[i] = true 로 메모
9. 인수로 전달받은 깊이 (=i) 와 다르고, 전달받은 컴퓨터와 연결되어 있으며(computers[i][j]==1), 이전에 방문한 적이 없을때(check[j]==false)
10. 상태가 바뀐 check 배열을 리턴한다.
11. 만약 위 조건문에 해당하지 않는다면 네트워크가 연결되지 않은 상태이므로 재귀 호출을 하지 않는다.
12. 재귀 호출을 했다는 것은 네트워크가 이전 노드와 연결되어 있다는 의미이므로 dfs 를 호출하는 함수에서 answer++ 을 해준다. 이는 네트워크가 끊어질 때 재귀 호출이 종료되며, 이전까지 기록된 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;
  }

}