[B0J]숨바꼭질 3(13549번)

티어 : gold 5
정답여부 : 정답
알고리즘 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 데이스크라, 최단경로, 0-1 너비우선탐색
시간 제한 : 2초

💡문제

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

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

 

💡입력

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

 

💡출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

💡예제 입력1

5 17

 

💡예제 출력1

2

 

💡문제 분석 요약

• 이어지는 숨바꼭질 문제와 같음 차이점은 순간이동은 0초라는 가중치라는점으로 최소 시간 경로 탐색: 순간이동은 가중치가 0이므로, 이를 먼저 처리하면 더 빠르게 목적지에 도달할 수 있는 가능성이 높습니다.

 

💡알고리즘 설계

1. 각 숫자를 입력 받음
2. tele을 먼저 해줌 가중치가 0 왜냐하면 최소 시간 경로을 탐색하며 더 빠르게 목적지에 도달 할 수 있음
   • 만약 순간이동을 나중에 처리한다면, 이미 1초를 소모함
3. 다음 back, front를 배열로 만들어 for문으로 설정 가중치 1

 

💡시간복잡도

• O(N)

 

💡코드

import java.util.*;
import java.io.*;

public class Main {
	static int subin , brother;
	static int[] arr = new int[100001];
	static boolean[] visit = new boolean[100001];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        subin = Integer.parseInt(st.nextToken());
        brother = Integer.parseInt(st.nextToken());
        
        bfs(subin);
        System.out.println(arr[brother]);
	}
	private static void bfs(int start) {
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(start);
		visit[start] = true;
		while(!que.isEmpty()) {
			int location = que.poll();
			if(location == brother) {
				return;
			}
			int back = location - 1;
			int front = location + 1;
			int tele = location * 2;
			int[] nextLocations = {back, front};
			for (int next : nextLocations) {
                if (next >= 0 && next <= 100000) {
                    if (!visit[next]) {
                        que.offer(next);
                        visit[next] = true;
                        arr[next] = arr[location] + 1;
                    } 
                }
            }
			if (tele >=0 && tele <= 100000 && !visit[tele]) {
				que.offer(tele);
				visit[tele] = true;
				arr[tele] = arr[location];
			}
		}
	}
}

 

💡 틀린 이유

덱을 이용한 방법도 있어서 한번 찾아봤다. 이러한 방식이 0-1 BFS 알고리즘 유형이라는것을 알게됬다.

 

💡 틀린 부분 수정 or 다른 풀이

import java.util.*;
import java.io.*;

public class Main {
    private static int start;
    private static int end;
    private static int[] distInfo;
    private static boolean[] visit;
    private static int max = 100_000;

    public static void main(String[] args) throws IOException {
        // 5 17
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        visit = new boolean[max * 2 + 1];
        distInfo = new int[max * 2 + 1];
        bfs13549();
    }

    private static void bfs13549() {
        Deque<Integer> dq = new ArrayDeque<>();
        visit[start] = true;
        dq.addLast(start);

        while (!dq.isEmpty()) {
            int current = dq.removeFirst();
            if (current == end) {
                System.out.println(distInfo[current]);
                System.exit(0);
            }

            int next = current * 2;
            if (next < max * 2 + 1 && !visit[next]) {
                visit[next] = true;
                distInfo[next] = distInfo[current];
                dq.addFirst(next);
            }

            next = current + 1;
            if (next < max * 2 + 1 && !visit[next]) {
                visit[next] = true;
                distInfo[next] = distInfo[current] + 1;
                dq.addLast(next);
            }

            next = current - 1;
            if (next >= 0 && !visit[next]) {
                visit[next] = true;
                distInfo[next] = distInfo[current] + 1;
                dq.addLast(next);
            }
        }

    }
}

 

 

💡 느낀점 or 기억할정보

신기한 알고리즘 유형에 대해 공부하는거 같다.