[Java] 백준 1697번 [숨바꼭질] 자바
백준 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는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17
예제 출력 1
4
생각하기
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와 테스트케이스가 다르다는 것을 알게되었는데,
숨바꼭질2에서는 Range_check 함수에서 next_time < 100000
으로 해도 통과가 되는데, 숨바꼭질1에서는 '맞았습니다'가 나오지 않는다.
얼떨결에 알게됬지만, 범위 틀리지 않도록 주의 좀 해야될듯
이거 때문에 숨바꼭질1에서 계속 틀렸는데, 범위가 틀렸다는걸 한참뒤에 알았음..
next_time <= 100000
로 수정을
TMI
순간이동 앞으로만 할줄아는거 실화냐?
진짜 충격 실화다 수빈아
오늘도 역시 이해가 안되는 바람에 손으로 써보는 노가다를 자행..
코드
BFS
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
Author And Source
이 문제에 관하여([Java] 백준 1697번 [숨바꼭질] 자바), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@lifeisbeautiful/Java-백준-1697번-숨바꼭질-자바
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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
Author And Source
이 문제에 관하여([Java] 백준 1697번 [숨바꼭질] 자바), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lifeisbeautiful/Java-백준-1697번-숨바꼭질-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)