[백준]12851번 숨바꼭질2
수빈이는 현재 점 N(0이상 10만 이하)에 있고, 동생은 점 K ( 0이상 10만 이하 )에 있다.
수빈이는 걷거나 순간이동이 가능하다.
- x-1
- x+1
- 2 * x
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는,
- 가장 빠른 시간은 몇 초 후인지
그리고,
- 가장 빠른 시간으로 찾는 방법은 몇가지인지
구하는 프로그램을 작성하라
예제
5 17
// 정답 : 4 2
첫 번째 : 5 -> 4 -> 8 -> 16 -> 17
두 번째 : 5 -> 10 -> 9 -> 18 -> 17풀지 못했다
1시간 동안 생각했으나 풀지 못했다.
일주일 넘게 문제를 풀지 않아 감을 잃었다는 생각이 든다.
현재 생기는 문제는 무엇일까???
depth를 생각하고 있었다면서... DFS로 풀었던게 문제 같다. BFS로 해야지 10만 까지 파고들면서도 정답을 구하지 못하는 경우가 생기지 않는다.
N이 1, K가 100000인 경우를 생각 해 보자
- 특정 x 는 한 번 만 방문하게 할 수는 없다.
- 하지만 { 같은 개수의 연산(cnt) } 을 통해서, { 특정 x에 방문 }하는 경우에도 뒤의 로직을 중복 실행하는 것을 피하게 할 수는 있다. —> pathcnt 라는 테이블을 추가
- 그런데 이러한 중복을 피하게 하더라도, 결국에는 재귀호출을 몇 천 개 이상을 중복호출하게 되는 경우가 생기고 만다.
- 이는, 2*x 를 호출하고는
- x +1 을 호출하다보니, 10만 까지 끝까지 호출하게 되기 때문이다.
풀이
- 현재 이런 문제가 생기는 것은, 나는 같은 depth의 것들을 먼저 방문하는 bfs로 생각하고는 구현을 dfs로 해 놓았었기 때문이었다.............. 이번주는 정신을 다시 찾아가는 과정이라 생각하자 ^^;;;
k외의 수에 대해서는 중복 방문을 하지 않도록 한다. ❌ —> 같은 depth에서의 중복방문은 허용해 놓아야 한다. 따라서, visit[next]= true를 체크하는 시점이 중요하다
- 가장 빠른 시간으로 찾는 방법은 몇가지인지 또한 구해내야 하기 때문에, 같은 depth에서의 중복방문을 허용해 두어야, 이 개수 또한 구할 수 있다.
- bfs로 접근을 하게 되면, k에 가장 처음 도달할 때의 depth가 가장 낮은 depth다.
- k 를 방문한 depth를 넘어간다면 종료한다.
import java.io.*;
import java.util.*;
public class Main{
public static int n=0,k=0;
public static int[] ops = new int[]{-1,+1,0};
public static int minCnt=0;
public static int minDepth = Integer.MAX_VALUE;
public static boolean[] visit = new boolean[100001];
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
}
public static void solve(){
if(n==k){
minCnt++;
minDepth=0;
return;
}
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{n,0}); // 현재 위치, depth
visit[n]=true;
int[] cur=null;
int next=0,nd=0; // next : 다음 방문 숫자, nd : next를 방문할 때의 depth
while(q.isEmpty()==false){
cur = q.poll();
ops[2]=cur[0];
// 같은 depth의 것들은 모두 들어올 수 있도록 하기 위해 visit을 여기에 위치시킨다
visit[cur[0]]=true;
for(Integer op : ops){
next = cur[0]+op;
nd = cur[1]+1;
if(next<0 || next>100000)continue;
//minDepth보다 큰 depth에서 방문하게 된다면 pass한다
if(minDepth<nd) continue;
// k를 방문하게 되는 경우
if(next == k ){
// 첫 번째 방문이 아닌 경우
if(minDepth==nd) minCnt++;
else {
// 첫 번 째 방문인 경우
minDepth = nd;
minCnt++;
}
// k 에서의 이동으로 다시 k를 방문하는 것은 더 깊은 depth에서의 방문 -> 최소가 아니다
// 따라서 k에서는 더 이상 이동하지 않는다.
continue;
}
// visit 체크는, q에서 꺼낼 때에 수행한다.
// 따라서, 같은 depth에서 중복 방문하는 것은 허용할 수 있다 -> 그래야, 최소연산으로 찾는 방법의 개수까지 구할 수 있다.
if(visit[next]) continue;
q.add(new int[]{next,nd});
}
}
}
public static void main(String[] args)throws IOException {
setting();
solve();
System.out.println(minDepth);
System.out.println(minCnt);
}
}