[99클럽 코테 스터디 7일차 TIL] BFS

📖 오늘의 학습 키워드
BFS

오늘의 회고

문제

[네트워크]
https://school.programmers.co.kr/learn/courses/30/lessons/43162

나의 해결

import java.util.*;
class Solution {
    public boolean[] visited;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                answer++;
                visited[i] = true;
                bfs(i, n, computers);
            }
        }
        return answer;
    }
    public void bfs(int start, int n, int[][] computers) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        while(!q.isEmpty()){
            int now = q.poll();
            for(int i = 0; i < n; i++) {
                if(!visited[i] && computers[now][i] == 1) {
                    visited[i] = true;
                    q.offer(i);
                }
            }
        }
    }
}

먼저, 반복문을 이용해 0부터 n-1까지의 컴퓨터 중 아직 방문하지 않은 컴퓨터가 있는지를 확인한다. 만약 있다면 네트워크의 개수를 하나 늘리고 BFS를 이용해 해당 컴퓨터와 같은 네트워크상에 있는 컴퓨터를 찾고 그 컴퓨터에 대한 방문 처리를 한다.

새로 학습한 내용

BFS를 복습할 수 있었다.