숨바꼭질(1697번)

• 티어 : Sliver 1
• 정답여부 : 오답
• 알고리즘 유형 : 그래프 이론, 그래프 탐색,너비 우선 탐색
• 시간 제한 : 2초

💡문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

💡문제요약

수빈이는 뒤로 앞으로 순간(?)이동을 통해 동생이 있는 위치까지 빠른시간안에 갈수 있는 최소 시간을 구하면 되는 문제

💡알고리즘 설계

해당 문제는 인근으로 구현을 하는 문제로 BFS 문제인걸 눈치를 챘다. (근데 BFS를 알면 뭐함 구현을 못하는데..😢)

• N : 수빈이 위치
• K = 동생 위치
• location : 현 수빈이 위치
• back : 뒤로 이동 -1
• front : 앞으로 이동 +1
• tele : 순간이동 *2

1. 수빈이 위치로 큐에 값을 넣어주며 방문을 표시
2. location에 현재 수빈이의 위치를 넣어준다
3. 현재 location에 -1 , 1 , *2 씩 이동한 거리를 back , front , tele 에 값을 넣어준다.
4. 만약 back , front, tele 값들이 0보다 크고 100,000 작으면 que에 추가
5. 방문했다고 표시
6. 현재 위치에 새로운 위치까지 도달한 시간 +1초를 저장
7. 동생이 있는곳 까지 걸린 최소 시간을 출력

💡작성코드

• Java

import java.util.*;
import java.io.*;
public class Main{
	static int N, K;
	static int arr[];
	static boolean visit[];
	static int time;
	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());
		arr = new int [100001];
		visit = new boolean[100001];
		bfs(N);
		System.out.println(time);
	}
	public static void bfs(int start) {
		Queue<Integer> que = new LinkedList<>();
		int next_x;
		que.offer(start);
		visit[start] = true;
		while(!que.isEmpty()) {
			int location = que.poll();
			if(location == K) {
				return;
			}
			int back = location - 1;
			int front = location + 1;
			int tele = location * 2;
			if (back >=0 && back <= 100000 && !visit[back]) {
				que.offer(back);
				visit[back] = true;
				time++;
			}
			if (front >=0 && front <= 100000 && !visit[front]) {
				que.offer(front);
				visit[front] = true;
				time++;
			}
			if (tele >=0 && tele <= 100000 && !visit[tele]) {
				que.offer(tele);
				visit[tele] = true;
				 time++;
			}		
		}	
	}
}

💡시간복잡도

O(N)

💡틀린 이유 or 수정할 부분

고냥 이동할때마다 time++ 해서 출력하면 되는거 아니야? 낄낄 하고 했다가 38초가 나오는 기적을 보았다. ㅋ 항상 잘 하다가도 결국 마지막에 이렇게 큰 실수를 한다. 생각을 해보다 큐 요소를 꺼낼때마다 time이 증가한다. 즉 수빈이가 arr 배열에 각 위치에 도달하기까지 걸린 시간을 저장해야 한다. 위치에 처음 도달했을 때, 그 위치에 도달하기까지 걸린 시간을 arr에 저장하고, 이 시간을 이용하여 다음 위치에 도달하는 데 필요한 시간을 계산해야 하면 된다..

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

• Java

import java.util.*;
import java.io.*;
public class Main{
	static int N, K;
	static int arr[];
	static boolean visit[];
	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());
		arr = new int [100001];
		visit = new boolean[100001];
		bfs(N);
		System.out.println(arr[K]);
	}	
	public static void bfs(int start) {
		Queue<Integer> que = new LinkedList<>();
		int next_x;
		que.offer(start);
		visit[start] = true;
		while(!que.isEmpty()) {
			int location = que.poll();
			if(location == K) {
				return;
			}
			int back = location - 1;
			int front = location + 1;
			int tele = location * 2;
			if (back >=0 && back <= 100000 && !visit[back]) {
				que.offer(back);
				visit[back] = true;
				arr[back] = arr[location] + 1;
			}
			if (front >=0 && front <= 100000 && !visit[front]) {
				que.offer(front);
				visit[front] = true;
				arr[front] = arr[location] + 1;
			}
			if (tele >=0 && tele <= 100000 && !visit[tele]) {
				que.offer(tele);
				visit[tele] = true;
				 arr[tele] = arr[location] + 1;
			}			
		}
	}
}

💡느낀점 or 기억할 정보

BFS, DFS 구분방법

1. BFS : 구현 방법으로 일단 최단 거리를 찾는 경우
2. DFS : 모든 노드를 다 방문해야 할 경우

항상 잘 구현했다가 문제에 포인트를 못 보고 틀린 경우가 많은거 같다 ㅜㅜ 생각보다 푸는데 오래 걸리고 구현도 힘들었다. 문뜩 든 생각이지만 이 문제를 DFS로는 어떻게 풀어야 할지는 감이 안 온다…