[PGS] 네트워크 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;

        boolean[] used = new boolean[n];
        // 방문하지 않은 (네트워크에 포함되지 않은) 모든 컴퓨터에 대해 BFS 수행
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            bfs(i, computers, n, used);
            // BFS 탐색을 수행했으면 네트워크가 생성된 것 -> 개수 증가
            answer++;
        }
        return answer;
    }

    private void bfs(int start, int[][] computers, int n, boolean[] used) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        used[start] = true;

        while (!q.isEmpty()) {
            int now = q.poll();
            for (int i = 0; i < n; i++) {
                // 같은 컴퓨터 번호이거나 연결되어있지 않거나 이미 사용중인 경우 무시
                if (isEqual(now, i) || !isConnect(computers[now][i]) || used[i]) continue;
                // 방문처리 후 큐에 추가
                used[i] = true;
                used[now] = true;
                q.offer(i);
            }
        }
    }

    private boolean isEqual(int intValue1, int intValue2) {
        return intValue1 == intValue2;
    }

    private boolean isConnect(int intValue) {
        return isEqual(1, intValue);
    }
}

📄 해설

접근

• BFS 를 사용하여 푸는 문제. Lv3 이라서 겁먹었는데, 생각보다 접근이 단순했다.
• 방문하지 않은 모든 컴퓨터에 대해 BFS 를 수행하면 된다.
• BFS 가 수행되는 경우는 네트워크가 하나 추가된 것이므로 개수를 증가한다.
• 문제에서 주어진 조건대로, 같은 번호가 아니고, 다른 네트워크에 포함되지 않고, 연결되어있으면 큐에 넣고 BFS 를 계속 수행한다.

과정

• 접근과 과정이 동일하므로 생략하겠음