BFS 기본 예제

 

1. 기본 형태

- 아래의 경우 3가지 경우의 수를 나타내는 상태트리

- ch배열을 사용하는 이유? : 중복된 트리를 생성하면 성능상 손해가 크다. (대신 메모리를 점유)

- Q에서 현재값을 읽은 뒤, 계산된 값을 집어 넣는 것이 포인트.

class Main {

	static int n,m;
	int [] dis = {1, -1, 5};
	static int [] ch;//중복 방지용
	Queue<Integer> q = new LinkedList<>();
	//3가지 경우의 수, L은 최단거리를 의미함.
	public int  BFS ( int start, int end ) {
		//제약사항으로 주어짐
		ch = new int[10001]; 
		//초기 상태 저장.
		ch[start] = 1;
		q.offer(start);
		int L = 0;

		//q가 마를 때 까지 돌린다.
		while(!q.isEmpty()) {
			
			 int len = q.size();
			 for (int i = 0 ; i < len ; i ++) {
				 int pos = q.poll();
				 
				 //최종 거리에 도달했을 때, Level의 값이 최단거리가 된다.
				 if( pos == end) return L;
				 
				 //각 경우의 수에 대해 계산하여 q에 다시 저장.
				 for (int d : dis) {
					 int nx = pos+d;
					 if( nx>=1 && nx<=10000 && ch[nx] == 0) {
						 //핵심, 다음거리를 계산하여 다시 q에 넣어줌.
						 ch[nx] = 1;
						 q.offer(nx);
					 }
				 }
			 }			
			L++;
		}
		return L;
	}

	
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();

		System.out.println( M.BFS(n, m) );
	}
}

 

 

 

//이진트리, 최단거리의 말단 노드 탐색


public int BFS( root ){
	Queue<Node> Q = new LinkedList<>();
    Q.offer(root);
    int L = 0;
    while( !Q.isEmpty()){
    	int len = Q.size();
        for ( int i = 0 ; i<len; ++i){
        	Node cur = Q.poll();
            if( cur.lt==null && cur.rt==null) return L; // 말단 노드 찾기
            if( cur.lt!=null) Q.offer(cur.lt);
            if( cur.rt!=null) Q.offer(cur.rt); // 레벨마다 2n승 증가.
            
        }
        L++;
    }
    return 0;
}