ITM_SPRING [Hacker Rank] Breadth first search_ 넓이 우선 탐지

BFS( Breadth first search) 는 가장 가까이에 있는 것 부터 차례대로 검색 하여 들어가는, 일종의  dynamic programming 에 의거한다. 

 

루트 노드에서 부터 하나의 edge로만 연결 된 노드부터 검색하는 것. 그것이 bfs 알고리즘이다. 즉, 깊게 탐색하기 이전에 가깝고 넓게 탐색을 하는 것이다. 

*다익스트라 알고리즘과 매우 유사하다* 

 

해당 코드는 ITM_2021_spring_algorithm 에 기인함으로 자바로 구현하였다. 

 

해당알고리즘은 Queue와 linked list 를 활용하였다. Queue를 활용하는 이유는 각 지점을 queue에 넣는 순서대로 검색하기 위해서, 즉 하나의 프로세스를 관리하기 위해서 이다. 

 

BFS를 다음의 예시로 구현화 하여 설명하였다.  

 

 

해당 그림처럼 구현하기 위해 다음을 정확히 하고자 하였다. 

 

1. 0과 인접한 노드들을 방문하였는지 검사하고 만약 방문하지 않았다면 queue에 add() 한다. 

2. 0의 노드 검사를 끝냈으면 queue poll() 을 하여 큐에 적재된 0 과 인접한 노드를 확인한다. 

3. 해당 과정을 queue에 적재된 값이 없을 때 까지 반복한다. 

 

* 또한 edge로 연결 되었는지 쉽게 파악하고자 matrix 형태로 나타내었다.*

if connected , 1 / else , 0  

ex

[ 0 , 1 , 1 , 0 , 1]

[ 1 , 1 , 0 , 0 ,0]

[1 , 1 , 0 , 1 , 0 ] 

[0 ,0 ,1 , 0 , 1  ]

[ 1 , 0 , 1 , 1 , 0]

 

 

package shortest_reach;
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class solution {

		
	
    // Complete the bfs function below.
    static int[] bfs(int n, int m, int[][] edges, int s) {
    	
    	int start = s-1;
    	int[] way = new int[n];
    	
    	boolean[] boo = new boolean[n];
    	Queue<Integer> queue = new LinkedList<Integer>();
    	int[][] ed = new int[n][n];
    	for( int i = 0 ; i < edges.length ; i ++) {
    		int f = edges[i][0] -1;
    		int z = edges[i][1] -1;
    		
    		ed[f][z] = 1;
    		ed[z][f] = 1;
    	}
    	
    	
    	s = s-1;
    	
    	queue.add(s);
    	boo[s] = true;
		
    	
    	while(!queue.isEmpty()) {
    		s = queue.poll();
        	for (int i = 0 ; i < ed[s].length ; i ++) {
	    		if (ed[s][i] == 1 & boo[i] == false) {
	    			
	    			way[i] = way[s]+1;
	    			boo[i] = true;
	    			queue.add(i);
	    		}	
	    	}
    	}
    	LinkedList<Integer> way_linked = new LinkedList<Integer>();
    	for(int i = 0 ; i <n ; i ++ ) {
    		if (way[i] == 0) {
    			way_linked.add(-1);
    		}
    		else {
    		way_linked.add(way[i]*6);
    		}
    	}
    	way_linked.remove(start);
    	
    	int[] a = new int[way_linked.size()];
    	
    	Iterator<Integer> iter = way_linked.iterator();
    	int cnt = 0 ;
    	while(iter.hasNext()){//다음값이 있는지 체크
    		int k = iter.next();
    		a[cnt] = k;
    	
    		cnt = cnt+1;
    	}
    	return a;	
    }
}

 

또한 출력을 위하여 LinkedList를 활용하였다. 

자바에서는 파이썬과 같이 쉬운 array control을 허용하지 않기에, array에 있는 값을 쉽게 지우고 추가할 수 없다. 따라서 linkedlist의 연결 값을 활용하여 지우고 추가를 쉽게 하도록 노력하였다. 

 

* java에서 자료구조를 다룰 때에는 linked list , double linked 등을 활용할 수 있도록 하여야 겠다. *