[백준 1697] 숨바꼭질 (JAVA)

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

1697번: 숨바꼭질

 

이 문제는 수빈이와 동생사이의 최단거리를 찾는 문제이므로 BFS 로 접근하는것이 푸는것에 용이하다.

 

 

수빈이가 한번에 이동한 범위는 현재위치 + 1 , 현재 위치 - 1 , 현재위치 * 2 이므로

해당 3가지 경우를 인접한 정점으로 생각해서 너비우선탐색으로 풀면된다.

 

전체 범위는 0 ~ 100,000 이므로 탐색할 배열의 길이를 정적으로 할당하겠다.

 

	static final int len = 100_001;
	static int n,k,front,rear;
	static int[] visit = new int[len];
	static int[] queue = new int[len];
	static int[] loc = new int[3];

 

 

현재 위치는 이동한 거리가 없으므로 0 부터 시작해야 하지만 방문처리를 위해 임의로 1을 넣어서

탐색을 시작할것이다.

마지막엔 동생의 위치까지 이동한 거리의 최소비용에서 임의로 1을 넣어줬던것을 다시 빼서 리턴해주겠다.

 

	static int bfs() {
		queue[rear++] = n;
		visit[n] = 1;
		

		return visit[k] - 1;
	}

 

 

 

너비에 대한 계산을 현재 정점에 대해 지속적으로 계산 해줘야 하므로 loc 배열에 차례로 값을 계산해 넣어준다.

 

그리고 넣어준 값에 대해 순회하며 범위와 방문여부를 확인하고 큐에 삽입해준다.

 

	static int bfs() {
		queue[rear++] = n;
		visit[n] = 1;
		

			int node = queue[front];
			queue[front++] = 0;
			front%=len;
			
			loc[0] = node + 1;
			loc[1] = node - 1;
			loc[2] = node << 1;
			
			for(int i = 0; i < 3; i++) {
				if(loc[i] >= 0 && loc[i] < len && visit[loc[i]] == 0) {
					queue[rear++] = loc[i];
					rear%=len;
					visit[loc[i]] = visit[node] + 1;					
				}
			}

		return visit[k] - 1;
	}

 

 

남은 것은

 

큐가 비워질때까지 반복이다.

 

	static int bfs() {
		queue[rear++] = n;
		visit[n] = 1;
		
		while(visit[k] == 0) {
			int node = queue[front];
			queue[front++] = 0;
			front%=len;
			
			loc[0] = node + 1;
			loc[1] = node - 1;
			loc[2] = node << 1;
			
			for(int i = 0; i < 3; i++) {
				if(loc[i] >= 0 && loc[i] < len && visit[loc[i]] == 0) {
					queue[rear++] = loc[i];
					rear%=len;
					visit[loc[i]] = visit[node] + 1;					
				}
			}
		}
		return visit[k] - 1;
	}

 

 

예제에 대해 테스트 해보겠다.

 

 

 

문제없이 출력값이 나오는것을 확인 할 수 있다.

 

 

아래는 코드의 전문이다.

 

package boj2;

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

public class Boj1697_2 {
	
	/*
	 * bfs 풀이
	 * 제출 完
	 */
	
	static final int len = 100_001;
	static int n,k,front,rear;
	static int[] visit = new int[len];
	static int[] queue = new int[len];
	static int[] loc = new int[3];
	
	static int bfs() {
		queue[rear++] = n;
		visit[n] = 1;
		
		while(visit[k] == 0) {
			int node = queue[front];
			queue[front++] = 0;
			front%=len;
			
			loc[0] = node + 1;
			loc[1] = node - 1;
			loc[2] = node << 1;
			
			for(int i = 0; i < 3; i++) {
				if(loc[i] >= 0 && loc[i] < len && visit[loc[i]] == 0) {
					queue[rear++] = loc[i];
					rear%=len;
					visit[loc[i]] = visit[node] + 1;					
				}
			}
		}
		return visit[k] - 1;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		in.close();
		
		System.out.print(bfs());
	}

}