BFS
- 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한번 씩 방문하는 방법이다
- 루트 노드에서 시작하여 인접한 노드 부터 탐색하는 특징을 가지고 있다.
- 재귀적으로 동작하지 않으며 주로 큐 자료구조를 사용하여 구현한다.
문제와 코드를 통해서 알아보겠다
- 백준 (13549번) 숨바꼭질 3
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
풀이
package BFS; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringTokenizer; public class Hide3 { static int time; static void bfs(int[] loc,int k){ Queue<int[]> q = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]); q.offer(loc); // bfs -> 우선순위 큐로 구현 while(!q.isEmpty()){ int[] nLoc = q.poll(); if(nLoc[0] == k) { time = nLoc[1]; break; } if(nLoc[0]-1 >= 0){ q.offer(new int[]{nLoc[0]-1,nLoc[1]+1}); } if(nLoc[0]+1 <= 100000){ q.offer(new int[]{nLoc[0]+1,nLoc[1]+1}); } if(nLoc[0]*2 <= 100000 && nLoc[0]*2 < k){ q.offer(new int[]{nLoc[0]*2,nLoc[1]+0}); } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()," "); time = 0; int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); bfs(new int[]{n,0},k); System.out.println(time); } }