[B0J]숨바꼭질(1697번)

티어 : Sliver 2
정답여부 : 오답
알고리즘 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
시간 제한 : 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

 

💡문제 분석 요약

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

💡알고리즘 설계

1. 해당 문제는 인근으로 구현을 하는 문제로 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. 동생이 있는곳 까지 걸린 최소 시간을 출력

💡시간복잡도

• O(N)

💡코드

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++;
			}
				
			
		}
		
	}

}

💡 틀린 이유

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

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

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로는 어떻게 풀어야 할지는 감이 안 온다…