[BAEKJOON] 1697번 숨바꼭질

---

 

초기 수빈이가 있는 위치  N 과 동생의 위치 K를 보자.

수빈이가 N-1 또는 N+1 또는 N*2 위치로 이동할 수 있으니 5에서 17로 가는 경우를 그림으로 그려본 것이다.

모든 배열은 0으로 초기화한 후, 해당 위치에 방문한 적이 있으면 넘어가고 그렇지 않다면 큐에 넣어 다음 방문 위치를 저장한다.

큐에서 다음 방문 위치를 꺼내어 해당 인덱스에 지금까지의 움직인 거리에 1을 더하여 저장하는 과정을 반복한다.

다음 방문할 위치가 동생이 있는 곳이라면 즉, 동생이 있는 인덱스 위치가 0이 아니라면 반복을 중단하고 이동한 거리를 반환하여 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int visited[], K;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		visited = new int [100005];
		
		System.out.println(bfs(N));
	}
	static int bfs(int n) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(n);
		
		while(!q.isEmpty()) {
			int current = q.poll();
			// 동생이 있는 위치 K를 방문한 적 있으면 나가기
			if(visited[K] != 0) break;
			// 인덱스 범위 안 벗어나고, 방문한적 없어야 큐에 삽입
			if(current-1>=0 && visited[current-1]==0) {
				q.add(current-1); 
				visited[current-1]=visited[current]+1;
			}
			if(current+1<visited.length && visited[current+1]==0) {
				q.add(current+1);
				visited[current+1]=visited[current]+1;
			}
			if(current*2<visited.length && visited[current*2]==0) {
				q.add(current*2);
				visited[current*2]=visited[current]+1;
			}
		}
		// 동생 위치까지의 이동 횟수 반환
		return (K==n)?0:visited[K];
	}
}

 

[출처]

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질