[백준] 12851 / 13913. 숨바꼭질 (골드4) - BFS, Stack

Kiefer Sol·2024년 8월 10일

목록 보기

27/35

12851. 숨바꼭질2 (골드4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	60158	16967	11799	25.733%

13913. 숨바꼭질4 (골드4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	50463	16878	11850	30.885%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

12851) 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

13913) 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

12851) 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.
13913) 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

12851. 예제 입력
5 17

12851. 예제 출력
4
2

13913. 예제 입력
5 17

13913. 예제 출력 (스페셜 저지)
4
5 10 9 18 17

13913. 예제 출력 (스페셜 저지)
4
5 4 8 16 17

풀이

코드

동생을 찾는 가장 빠른 방법을 찾기 위해 parent 배열 선언
수빈이 더 뒤쪽에 있으면 후퇴하는 방법 밖에 없다. -1씩 후퇴하기
BFS 호출, 반복문 돌면서 -1, 1, 2 더해가면서 next 구하기
3.1. 범위 내에 있고 동생을 만나면 cnt 증가 (12851), 최소시간 갱신
최소시간이 0이거나, 갱신시간==이전시간+1 일 때 큐에 넣거나, 시간 갱신
4.1. 다음 위치의 이전 위치는 현재 위치이다.
도착점 위치를 처음으로 parent 배열의 값을 stack에 넣고, 마지막에 빼면서 출력 => 경로출력

12851의 응용버전인 13913을 기준으로 코드를 작성한다.

public class Search_13913 {
	public static int N, K;
	public static int[] parent = new int[100001]; // 동생을 찾는 가장 빠른 방법을 찾기 위해 사용
	public static int[] time = new int[100001]; // 동생을 찾는 가장 빠른 시간을 찾기 위해 사용
	public static int minTime; // 가장 빠른 시간
    //public static int cnt; - 12851 가장 빠른 시간으로 찾는 방법의 갯수

	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()); // 수빈
		K = Integer.parseInt(st.nextToken()); // 남동생

		//수빈이 더 뒷쪽에 있으면 후퇴하는 방법 밖에 없다. -1씩 후퇴하기
		if (N >= K) {
			System.out.println(N - K); //minTime
			for(int i=N;  i>K; i--) {
				System.out.print(i+" ");
			}
			System.out.println(K);
			return;
		}
		
		//cnt = 0; - 12851
		minTime = Integer.MAX_VALUE;

		BFS();
		System.out.println(minTime);
        //System.out.println(cnt); - 12851
		
        
        // 도착점에서 츨발점까지 거슬러 올라가기
		Stack<Integer> stk = new Stack<Integer>();
		stk.push(K);
		int idx = K;
		
		while(idx!=N) {
			stk.push(parent[idx]);
			idx = parent[idx];
		}
		
        // 스택으로 거꾸로 경로출력
		while(!stk.isEmpty()) {
			System.out.print(stk.pop()+" ");
		}
		
		System.out.println();
		
	}

	public static void BFS() {
		Queue<Integer> que = new LinkedList<Integer>();
		
        // 시작위치 설정
		que.offer(N);
		time[N] = 1;

		while (!que.isEmpty()) {
			int now = que.poll();
			if (minTime < time[now])
				return;

			for (int i = 0; i < 3; i++) {
				int next = now; // * 시작점에서 다른걸 시도할 때마다, 다시 시작점으로 와야한다.
				if (i == 0) {
					next -= 1;
				} else if (i == 1) {
					next += 1;
				} else {
					next *= 2;
				}

				if (next < 0 || next > 100000)
					continue;

				if (next == K) { // 동생 만남
					minTime = time[now];
					//cnt++; - 12851
				}
				
				//time[next] > time[now] + 1 => 가능하긴 하지만 경우가 많아서 메모리초과
				if (time[next] == 0 || time[next] == time[now] + 1) {
					que.offer(next);
					time[next] = time[now] + 1; // 걸리는 시간 갱신
					parent[next] = now; // 다음 위치의 이전 위치는 현재 위치이다.
				}
			}

		}
	}

}