프로그래머스 - BFS 네트워크

JungWooLee·2022년 9월 20일
0

알고리즘

목록 보기
5/8
post-thumbnail

문제

알고리즘을 지난 5개월 동안 놓고있다가 최근 들어 다시 잡기 시작하면서 조금씩 예전의 감을 찾아가고 있는듯 하다.

네트워크 문제는 쉽게 말해 이어져 있는 노드들이 몇개가 있느냐를 묻는 문제이다
DFS, BFS 다양한 방법들이 있지만 접근하기 쉬운 BFS 를 통해 너비우선 탐색을 진행하였다


문제 접근

문제에서 요구사항 중 충족해야 하는 조건을 생각해보았다
1. 자기자신은 항상 연결되어있기에 항상 1, 즉 고려할 필요없음
2. 연결된 곳은 computers 배열의 인덱스로 접근하여 1인 곳을 파악
3. 그래프의 사이즈는 n*n 이기에 이를 고려하여 0 부터 n 까지 loop를 돌면서 탐색
4. 방문 여부는 따로 visited[] 배열을 두어 저장


문제 풀이

  1. static 전역 변수 설정하기
static boolean[] visited; // 방문 여부를 저장
static int[][] graph; // 컴퓨터 그래프 저장
static int n; // 컴퓨터의 개수 저장
  • bfs 는 void 로 설정할 것이기 때문에 미리 전역 변수를 정의합니다
  1. bfs 함수 만들기
  • 매게변수로 시작위치를 받아와 큐에 담고 방문처리
  • 큐에서 하나씩 꺼내와 방문하지 않은 곳중 연결된 곳을 큐에 담고 방문처리
	public static void bfs(int computer){
        // 자기자신은 항상 연결 되어 있으니 고려하지 않음
        Queue<Integer> queue = new LinkedList<>(); // 큐 생성
        queue.add(computer); // 시작 위치 큐에 담기
        visited[computer] = true; // 시작 위치 방문처리
        while(!queue.isEmpty()){
            // 큐가 비지 않을때 까지 계속
            int node = queue.poll(); // 큐에서 하나의 노드를 빼옴
            for (int i = 0; i < n; i++) {
                if(i!=node && !visited[i] && graph[node][i]==1){
                    // 만약 노드가 자기자신이 아니고, 방문한 적이 없으며 연결되어있다면 방문처리 후 큐에 담아준다
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
  1. 0~ n 까지 돌면서 방문하지 않았을 때 bfs 를 호출, 호출 횟수를 answer에 저장
	public static void main(String[] args) {
        // 샘플 그래프
        graph = new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
        // 전역 변수 값 지정
        n = graph.length;
        visited = new boolean[n];

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            // 만약 해당 컴퓨터가 방문한적 없는 컴퓨터라면 bfs를 수행하고 카운트 1증가
            if(!visited[i]){
                cnt++;
                bfs(i);
            }
        }

        System.out.println(cnt);
    }

전체코드

import java.util.*;

class Solution {
    static boolean[] visited;
    static int[][] graph;
    static int s;
    
    public static void bfs(int computer){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(computer);
        visited[computer] = true;
        
        while(!queue.isEmpty()){
            int node = queue.poll();
            for(int i=0; i<s; i++){
                if(i!=node && !visited[i] && graph[node][i]==1){
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        graph = computers;
        s = n;
        
        int answer = 0;
        
        for(int i=0; i<n; i++){
            if(!visited[i]){
                answer++;
                bfs(i);
            }
        }
        
        return answer;
    }
}

0개의 댓글