문제유형

BFS, 단순구현

문제풀이

모듈 2가지
1. BFS
   -. x+1, x-1, x*2 방문체크
   -. 방문하지 않았다면 큐에 대입
   -. 역추적을 위해 from[now] = next 형태로 저장, 재귀함수를 통해 마지막에 추적하기 위함 e.g) 1->2->3->4 면 from[4] = 3, from[3] = 2, from[2] =1 이런식

2. 역추적
   -. 재귀함수로 역추적

코드

package backjun;
import java.io.*;
import java.util.*;
public class BOJ_13913_숨바꼭질4 {
static void print(int n, int m, int[] from) {
if(n!=m) {
print(n, from[m], from);
}
System.out.print(m+" ");
}
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int begin = Integer.parseInt(st.nextToken());
int target = Integer.parseInt(st.nextToken());
Queue<int[]> q = new LinkedList<>();
int[] from = new int[100001];
boolean[] visit = new boolean[100001];
visit[begin] = true;
q.add(new int[] {begin,0});
while(!q.isEmpty()) {
int[] k = q.poll();
if(k[0]==target) {
System.out.println();
System.out.print(k[1]+" ");
print(begin,target,from);
}
if(k[0]+1<=100000 && visit[k[0]+1]==false) {
visit[k[0]+1] = true;
q.add(new int[] {k[0]+1,k[1]+1});
from[k[0]+1] = k[0];
}
if(k[0]-1>=0 && visit[k[0]-1]==false) {
visit[k[0]-1] = true;
q.add(new int[] {k[0]-1, k[1]+1});
from[k[0]-1] = k[0];
}
if(2*k[0]<=100000 && visit[2*k[0]]==false) {
visit[2*k[0]] = true;
q.add(new int[] {2*k[0], k[1]+1});
from[k[0]*2]=k[0];
}
}
}
}

'알고리즘' 카테고리의 다른 글

알고리즘 :: 신규 아이디 추천 (javascript)  (0) 2021.05.07
BOJ 1619, 최소비용구하기  (0) 2020.11.08
특정거리의 도시찾기  (0) 2020.11.07
멀쩡한사각형  (0) 2020.11.07
BOJ :: 1182(부분 수열의 합)  (0) 2020.10.26