네트워크

[문제 접근법]

- 트리 탐색 중 깊이 우선 탐색(DFS)을 이용하여 네트워크 개수를 반환하였다.

문제 설명

 

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

---

[구현 1]

- DFS 탐색 및 중복 방문을 막기 위해(boolean [] visit)을 이용하여 네트워크 개수를 구하였음

searchNetwork 함수가 재귀적으로 깊이 우선 탐색을 한다.

package com.codingtest.programmers.level3;

//https://programmers.co.kr/learn/courses/30/lessons/43162
public class Network {

    //DFS 탐색
    public int searchNetWork(int[][] computers, int pos, boolean[] visit) {
        visit[pos] = true;

        for (int j = 0; j < computers[pos].length; j++) {
            if (pos != j && !visit[j] && computers[pos][j] == 1) {
                searchNetWork(computers,j,visit);
            }
        }

        return 1;
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visit = new boolean[n]; //방문 여부 확인

        for (int i = 0; i < n; ++i) {
            if (!visit[i])
                answer += searchNetWork(computers, i, visit);
        }

        return answer;
    }

   
}

 

[구현 2]

- Que를 활용하여 컴퓨터를 1 ...n 까지 하나씩 넣어서 BFS탐색을 하였다. DFS와 동일하게 중복 연산을 막기 위해 visit 배열을 생성하여 체크하였음.

 	//BFS 탐색
    public int searchNetWorkBFS(int[][] computers, int n) {
        int count = 0;
        boolean[] visit = new boolean[n];
        Queue<Integer> que = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                que.add(i);
                count++;

                while (!que.isEmpty()) {
                    Integer network = que.poll();

                    for (int j = 0; j < computers[network].length; j++) {
                        if (network != j && !visit[j] && computers[network][j] == 1) {
                            visit[j] = true;
                            que.add(j);
                        }

                    }
                }
            }
        }


        return count;
    }

    public int solution(int n, int[][] computers) {
        return searchNetWorkBFS(computers, n);
    }