bfs 자바

bfs의 원리

 

1. 시작노드를 큐에 넣고 방문했다는 표시를 함

2. 큐에서 원소를 하나 빼고, 인접한 노드들에 대해 3번을 진행함

3. 방문했으면 아무것도 하지 않고, 방문하지 않았으면 원소를 큐에 넣고 방문했다는 표시를 함

4. 큐에 원소가 빌때까지 2번을 반복함

모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)

 

참고 블로그: https://blog.encrypted.gg/941

[실전 알고리즘] 0x09강 - BFS

 

 

 

1260번을 한 번 풀어보겠다

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

전체 코드

package com.example.demo.Week1;

import java.util.*;
import java.io.*;

class Main{
    static StringBuilder sb=new StringBuilder();
    static Queue<Integer> q=new LinkedList<>();
    static int[] visited;
    static int node, line, start;
    static int[][] arr;


    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        node=Integer.parseInt(st.nextToken());
        line=Integer.parseInt(st.nextToken());
        start=Integer.parseInt(st.nextToken());

        visited=new int[node+1];
        arr=new int[node+1][node+1];

        for(int i=0; i<line; i++){
            StringTokenizer str=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(str.nextToken());
            int b=Integer.parseInt(str.nextToken());

            arr[a][b]=1;
            arr[b][a]=1;
        }
        bfs(start);

        System.out.println(sb);

    }

    static void bfs(int start){
        q.add(start);
        visited[start]=1;

        while(!q.isEmpty()){
            start=q.poll();
            sb.append(start+" ");

            for(int i=1; i<=node; i++){
                if(visited[i]!=1 && arr[start][i]==1){
                    q.add(i);
                    visited[i]=1;
                }
            }

        }

    }

}

 

1. 시작노드를 큐에 넣고 방문했다는 표시를 함

q.add(start);

visited[start]=1;

 

2. 큐에서 원소를 하나 빼고 인접한 노드들에대해 3번진행

start=q.poll();

sb.append(start+" ");

 

 

3. 방문했으면 아무것도 하지 않고, 방문하지 않았으면 큐에 원소를 넣어주고 방문했다는 표시를 한다

for(int i=1; i<=node; i++){

if(visited[i]!=1 && arr[start][i]==1){

q.add(i);

q.visited[i]=1;

}

}

 

arr는

노드와 노드사이의 간선을 표시하는 2차원 배열이다

arr[start][i]가 1이면 간선이 존재한다는 것이다

간선이 존재하고 방문하지 않았을때만 큐에 넣어준 

 

 

4. 큐가 빌때까지 반복

while(!q.isEmpty())

{

 

}로 감쌈

 

 

참고 블로그 : https://infodon.tistory.com/96

[백준알고리즘-JAVA]1260번 풀이(DFS와 BFS) - 초보도 이해하는 풀이