백준 1697번
https://www.acmicpc.net/problem/1697
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
5 17
4
풀면서 느낀점인데, 진짜 BFS의 정석적인 문제가 아닌가, 라는 생각이 들었다.
DFS로는 푸는것이 힘들고,
수빈이가 찾으러 갈 수 있는 방법 3가지를 가지치기 형식으로 계속 퍼져나가면서 찾아가는 방식이다.
수빈이가 서 있는 곳N
을 출발점으로 생각하고,
arr[N]
만 1로 설정해준다.
그리고 출발점을 que
에 넣어주고 시작한다.
출발점에서 가중치를 더해주듯이 앞으로 나아갈 것이다.
그리고 수빈이가 동생을 만났을 때, 더해진 가중치의 최소값을 구하는 것이다.
que
에서 가장 먼저 K
와 마주치는 것이 곧 최소값이된다.
arr[next_time] == 0
이 3가지 조건을 고려해서
que
에 위치의 값을 넣으면서 que
가 빌 때까지 반복하면 된다.
min_time = Integer.MAX_VALUE/16;
으로 초기화한 것은
그냥 Integer.MAX_VALUE로 설정하면 +를 해주었을 때, Integer범위를 넘어서
Integer.MIN_VALUE 값으로 넘어가버리기 때문에, 그냥 /16을 넣어서 설정해줬다.
(딱히 의미는 없고 그냥 최댓값으로 초기화 한거임)
그리고 한가지 예외케이스를 잊지 말자.
수빈이가 동생보다 더 앞에 있을 때,
수빈이는 순간이동을 앞으로 밖에 못한다. 그럼 뒤로가는 것은 -1 밖에 못한다는 얘기니까.
if(N >= K) {
System.out.println(N-K);
return;
}
해당 조건을 넣어줘서 1걸음씩 뒤로 가는 계산을 해주면 된다.
숨바꼭질2에서는 Range_check 함수에서 next_time < 100000
으로 해도 통과가 되는데, 숨바꼭질1에서는 '맞았습니다'가 나오지 않는다.
얼떨결에 알게됬지만, 범위 틀리지 않도록 주의 좀 해야될듯
이거 때문에 숨바꼭질1에서 계속 틀렸는데, 범위가 틀렸다는걸 한참뒤에 알았음..
next_time <= 100000
로 수정을
순간이동 앞으로만 할줄아는거 실화냐?
진짜 충격 실화다 수빈아
오늘도 역시 이해가 안되는 바람에 손으로 써보는 노가다를 자행..
import java.io.*; import java.util.*; public class Main { static Queue<Integer> que = new LinkedList<>(); static int arr[] = new int[100001]; static int N, K; static int min_time; static int next_time; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); if(N >= K) { System.out.println(N-K); return; } BFS(); System.out.println(min_time); } // End of main private static void BFS() { min_time = Integer.MAX_VALUE/16; // 최단 시간 que.offer(N); arr[N] = 1; while( !que.isEmpty() ) { int time = que.poll(); if(min_time < arr[time]) { return; } for(int i=0; i<3; i++) { switch(i) { case 0: next_time = time + 1; break; case 1: next_time = time - 1; break; default: next_time = time * 2; } if(next_time == K) { min_time = arr[time]; return; } if( Range_check() && (arr[next_time] == 0 || arr[next_time] == arr[time] + 1) ) { que.offer(next_time); arr[next_time] = arr[time] + 1; } } } }// End of BFS // 범위 체크 static boolean Range_check() { return (next_time >= 0 && next_time <= 100000); } // End of Range_check } // End of class