BFS
최단 거리를 구하는 알고리즘이다.
BFS는 모든 가중치가1일때, 최단 거리를 구하는 알고리즘이다.
- 최소 비용 문제이어야 한다
- 간선의 가중치가 1이어야 한다
- 정점과 간선의 개수가 적어야 한다. (적다는 것은 문제의 조건에 맞춰서 해결할 수 있다는 것을
의미한다)
문제 1 ) 숨바꼭질
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17
예제 출력 1
4
내가한 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder builder = new StringBuilder();
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int max = 100001;
int N = Integer.parseInt(tokenizer.nextToken());
int K = Integer.parseInt(tokenizer.nextToken());
int[] check =new int[max];
Queue<Integer> q = new LinkedList<Integer>();
q.add(N);
check[N] = 1;
while(!q.isEmpty())
{
int current = q.remove();
if(current == K)
{
System.out.println(check[current]-1);
break;
}
if(current-1>=0&&check[current-1]==0 )
{
q.add(current-1);
check[current-1]=check[current]+1;
}
if(current+1<max&&check[current+1]==0 )
{
q.add(current+1);
check[current+1]=check[current]+1;
}
if(current*2<max&&check[current*2]==0 )
{
q.add(current*2);
check[current*2]=check[current]+1;
}
}
}
}과거에 내가한 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static final int MAX = 100000;
static class Location {
int n, distance;
public Location(int n, int distance) {
this.n = n;
this.distance = distance;
}
}
public static int BFS(int start_point, int last_point) {
boolean[] visited = new boolean[MAX + 1];
Queue<Location> will_visit = new LinkedList<Location>();
Location start = new Location(start_point, 0);
will_visit.add(start);
while (will_visit.size() > 0) {
Location current_point = will_visit.remove();
if (current_point.n == last_point)
return current_point.distance;
if (current_point.n < 0 || current_point.n > MAX)
continue;
if (visited[current_point.n])
continue;
visited[current_point.n] = true;
will_visit.add(new Location(current_point.n - 1, current_point.distance + 1));
will_visit.add(new Location(current_point.n + 1, current_point.distance + 1));
will_visit.add(new Location(current_point.n * 2, current_point.distance + 1));
}
return 0;
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int K = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int count = BFS(K, N);
System.out.print(count);
}
}
문제 2 ) 숨바꼭질4
문제
숨바꼭질과 같음 그치만 경로를 포함 해야함
출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.
예제 입력 1
5 17
예제 출력 1
4
5 10 9 18 17
내가한 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static final int MAX = 100000;
static class Location {
int n;
int past, distance;
public Location(int n,int past, int distance) {
this.n = n;
this.past = past;
this.distance = distance;
}
}
static HashMap<Integer, Location> map = new HashMap<Integer, Location>();
public static int BFS(int start_point, int last_point) {
boolean[] visited = new boolean[MAX + 1];
Queue<Location> will_visit = new LinkedList<Location>();
Location start = new Location(start_point,-1, 0);
will_visit.add(start);
map.put(start_point, start);
while (will_visit.size() > 0) {
Location current_point = will_visit.remove();
if (current_point.n == last_point)
{
map.put(current_point.n, current_point);
System.out.println(current_point.distance);
return current_point.n;
}
if (current_point.n < 0 || current_point.n > MAX)
continue;
if (visited[current_point.n])
continue;
visited[current_point.n] = true;
map.put(current_point.n, current_point);
will_visit.add(new Location(current_point.n - 1,current_point.n, current_point.distance + 1));
will_visit.add(new Location(current_point.n + 1,current_point.n, current_point.distance + 1));
will_visit.add(new Location(current_point.n * 2,current_point.n, current_point.distance + 1));
}
return 0;
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int K = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int n = BFS(K, N);
ArrayList<Integer> list = new ArrayList<Integer>();
while(true)
{
Location l = map.get(n);
list.add(n);
if(l.past==-1)
break;
n=l.past;
}
for(int i=list.size()-1; i>=0;i--)
System.out.print(list.get(i)+" ");
}
}풀이
주니어 개발자
0개의 댓글
