🔗 링크

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}}));
  }
}