[Programmers] 네트워크 - 깊이/너비 우선 탐색(DFS/BFS) - 2021.06.14

문제 링크 : Programmers
나의 풀이 : Git Solution

문제내용

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

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

풀이과정

초기구상

1. bfs로 돌면서 다음 방문할 노드를 찾고
2. 방문체크하고
3. 더이상 방문할곳이 없으면 리턴하고 cnt + 1
4. 이렇게 노드 수만큼 실행하면 될거같다

진행하며 수정된 내용

• 처음에는 computers에 값을 2로 수정해서 방문체크를 진행했으나
  메서드 내부에서 coms[depth][depth] == 2 이렇게 비교하는게 직관적이지 않고
  computers의 값을 변경했기 때문에 다시 활용할수 없음,
  computers를 원본으로 유지하려면 결국 2차원 배열에 대한 Deep Copy를 해야함
• 방문체크용 visitedArray를 따로 생성해서 사용하기로 함

최종형태

1. 노드수만큼 반복문 안에서 dfs 메서드 실행
2. 방문체크하면서 인접노드가 없어지면 1개의 네트워크로 cnt++ 처리

public static boolean isLinked(int[][] coms, int depth, int[] visited) {
        if (visited[depth] == 1) return false;

        visited[depth] = 1;
        for (int i = 0; i < coms[depth].length; i++) {
            if (coms[depth][i] == 1)
                isLinked(coms, i, visited);
        }

        return true;
}

실행결과

테스트 1 〉 통과 (0.03ms, 53.3MB)
테스트 2 〉 통과 (0.02ms, 52.5MB)
테스트 3 〉 통과 (0.05ms, 52.3MB)
테스트 4 〉 통과 (0.06ms, 52.1MB)
테스트 5 〉 통과 (0.02ms, 53MB)
테스트 6 〉 통과 (0.12ms, 52MB)
테스트 7 〉 통과 (0.03ms, 52.3MB)
테스트 8 〉 통과 (0.10ms, 52.6MB)
테스트 9 〉 통과 (0.06ms, 53.7MB)
테스트 10 〉 통과 (0.06ms, 52.9MB)
테스트 11 〉 통과 (0.35ms, 53.4MB)
테스트 12 〉 통과 (0.27ms, 53.1MB)
테스트 13 〉 통과 (0.24ms, 53.1MB)