[Java] 백준 1697번 [숨바꼭질] 자바

: ) YOUNG·2022년 4월 6일

알고리즘

목록 보기

84/417

백준 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

생각하기

풀면서 느낀점인데, 진짜 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