[프로그래머스] 네트워크(JAVA)

코딩테스트연습(DFS,BFS) - 네트워크

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

프로그래머스

문제 설명

컴퓨터들의 연결관계가 주어진 2차원 배열이 주어진다. 

서로 연결된 컴퓨터는 하나의 네트워크라고한다.

주어진 연결관계에 따른 네트워크의 개수를 구하는 문제이다.

예를 들어 컴퓨터의 연결관계가 위와같다면

네트워크는 총 3개가 된다.

---

문제 풀이

생각 과정

각 컴퓨터에 연결된 다른 컴퓨터를 타고 들어가서 하나의 네트워크로 묶어야하기 때문에 

너비우선탐색(BFS)로 풀기로 했다.

 

우선 각 컴퓨터마다 연결되어있는 다른 컴퓨터를 배열에 저장한다.

그리고 연결관계를 파악할 큐와 방문확인을 할 boolean 배열을 하나 설정한다.

그리고 1번 컴퓨터부터 n번 컴퓨터까지 다음 과정을 반복한다.

 

1. i번 컴퓨터를 방문하지 않았다면 큐에 넣고 새로운 네트워크가 생성된 것이므로 count를 늘려준다.

2. 큐에서 컴퓨터를 하나 꺼내 해당 컴퓨터에 연결된 다른 컴퓨터들을 모두 큐에 넣어준다. 

3. 2를 큐가 비게 될 때까지 계속 반복한다.

구현

class Solution {
    public int solution(int n, int[][] computers) {
        int cnt = 0;
        List<Integer>[] list = new ArrayList[n];	// 각 컴퓨터에 연결된 컴퓨터번호를 저장할 배열
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (computers[i][j] == 1) {
                    list[i].add(j);
                }
            }
        }
        boolean[] checked = new boolean[n];	// 방문체크를 할 배열
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (checked[i]) continue;	// 이미 포함된 컴퓨터면 넘어가기
            q.add(i);
            cnt++;	// i번 컴퓨터를 시작으로 하는 새로운 네트워크가 생성
            while (!q.isEmpty()) {
                int cur = q.poll();	// 현재 컴퓨터
                checked[cur] =true;
                for (int next : list[cur]) {	// 현재 컴퓨터에 연결된 컴퓨터 모두 체크 
                    if (checked[next]) continue;
                    checked[next] = true;
                    q.add(next);
                }
            }
        }
        return cnt;
    }
}