[알고리즘] Java / 백준 / 숨바꼭질2 / 12851
[알고리즘] Java / 백준 / 숨바꼭질2 / 12851
문제
접근 방식
트리 구조처럼 수빈이의 현재 위치에서 -1, *2, +1로 가는 경우의 수를 확인한다
bfs를 활용하여 수빈이의 위치와 시간을 가지는 배열을 큐에 담은 후 동생의 위치에 도달할 때 까지 -1, *2, +1로 수빈이를 옮기고 시간도 추가하여 다시 큐에 담는다.
수빈이가 처음으로 동생에게 도달했을 때의 시간을 저장하고 해당 시간과 같은 시간으로 동생에게 도달할 때마다 카운트를 한다. 또한 해당 시간보다 더 많은 시간을 가지는 배열이 탐색되면 while문을 빠져나간다
코드
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_12851 {
static int N,M;
static int time;
static int cnt;
static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
time = 100001;
cnt = 0;
visited = new boolean[100001];
bfs();
System.out.println(time);
System.out.println(cnt);
}
public static void bfs() {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {N,0});
while(!q.isEmpty()) {
int[] now = q.poll();
visited[now[0]] = true;
if(time < now[1]) break;
if(now[0] == M) {
if(time != now[1]) time = now[1];
cnt++;
}
if(now[0]-1 >=0 && !visited[now[0]-1]) q.add(new int[] {now[0]-1,now[1]+1});
if(now[0]*2 <= 100000 && !visited[now[0]*2]) q.add(new int[] {now[0]*2,now[1]+1});
if(now[0]+1 <= 100000 && !visited[now[0]+1]) q.add(new int[] {now[0]+1,now[1]+1});
}
}
}
Author And Source
이 문제에 관하여([알고리즘] Java / 백준 / 숨바꼭질2 / 12851), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-Java-백준-숨바꼭질2-12851저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)