숨바꼭질4
문제유형
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 |
댓글
이 글 공유하기
다른 글
-
알고리즘 :: 신규 아이디 추천 (javascript)
알고리즘 :: 신규 아이디 추천 (javascript)
2021.05.07 -
BOJ 1619, 최소비용구하기
BOJ 1619, 최소비용구하기
2020.11.08 -
특정거리의 도시찾기
특정거리의 도시찾기
2020.11.07 -
멀쩡한사각형
멀쩡한사각형
2020.11.07
댓글을 사용할 수 없습니다.