[Java]백준 16953번: A -> B (BFS, 너비 우선 탐색 알고리즘)

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

16953번: A → B

 

 

너비 우선 탐색(BFS, breadth-first search)
그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

기능	특징	시간 복잡도(노드 수: V, 에지 수: E)
그래프 완전 탐색	- FIFO 탐색 - Queue 자료구조 이용	O(V + E)

너비 우선 탐색의 핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복하기

 

---

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class j16953 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
	    long A=sc.nextInt();
		long B=sc.nextInt();
		System.out.println(BFS(A,B));
		
	}

	private static long BFS(long num, long B) {
		Queue<long[]> que=new LinkedList<>();
		que.add(new long[] {num,1});
		while(!que.isEmpty()) {
			long[] now=que.poll();
			if(now[0]==B) {
			  return now[1];
			}else if(now[0] <B) {
				que.add(new long[] {now[0]*2,now[1]+1});
				que.add(new long[] {now[0]*10+1,now[1]+1});
			}
		}
		return -1;
		
	}
}

 

풀이

2가지 방법 2를 곱하거나, 뒤에 1을 더하는 방법 중 B까지 최소의 방법으로 구하기 위하여 BFS 너비 우선 탐색 사용

 

- queue에 넣은 long [] 배열에서는 que[0]에는 값을 넣고 que[1]에는 깊이를 넣었다.

Queue<long[]> que=new LinkedList<>();

 

- 현재 큐에서 꺼낸 노드가 목표 B보다 작으면 큐에 값에 2를 곱하거나 뒤에 1을 붙이고  깊이에 +1 (2가지 방법) 추가

que.add(new long[] {now[0]*2,now[1]+1});
				que.add(new long[] {now[0]*10+1,now[1]+1});

 

-  최종 값이 B면 그 노드의 깊이를 출력하고 아니면 -1 출력

 

 

 

출처: 백준, Do it! 알고리즘 코딩 테스트 자바 편