[BackJoon] 백준 1697 숨바꼭질(BFS)

백준 BFS 문제

#1697- 숨바꼭질

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

사용한 개념

BFS개념를 응용했습니다.

우선 방문한 곳은 check 1차원 배열로 방문여부를 체크하여 방문하지 않은 곳만 방문을 하게끔 만들고, BFS 을 통해 방문하지 않은 곳을 계속해서 탐색하도록 합니다. 여기서 포인트는 방문할 때마다 몇번만에 해당 탐색지점에 왔는지 카운트를 해주는 것입니다. 

*2에서 5를 찾는 경우

예를 들어 2번에서 시작한다고 치고, 2번에서 *2를 해 4번으로 갔다면, 처음 2번에는 카운트 0을 저장하고 4번에 카운트는 0+1 = 1 입니다. 

다음 4번에서 +1을 했다면 5번에는 카운트 0+1+1 = 2 입니다. 이런식으로 2에서 시작해 5번으로 도착할때 카운트는 결국 카운트 2인 것입니다. 따라서 답은 2 입니다.

전체소스

package BackJoon.BackTracking;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BackJoon1697_BFS {

	static int size = 100001;
	static int[] v = new int[size];
	static boolean[] check = new boolean[size];
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int start = sc.nextInt(); //수빈이의 위치
		int target = sc.nextInt(); //동생의 위치
		
		
		for(int i=0; i<size; i++){
			v[i] = i;
		}
		
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		v[start] = 0;
		check[start] = true;
		
		int[] cal = {1,-1,2};
		while(!q.isEmpty()){
			int num = q.poll();
			int mvNum = 0;
			for(int i=0; i<3; i++){
				if(i==2){
					mvNum = num * cal[i];
				}else{
					mvNum = num + cal[i];
				}
				
				if(-1 < mvNum && mvNum <= 100000 && check[mvNum] == false){
					check[mvNum] = true;
					v[mvNum] = v[num] + 1;
					if(mvNum == target) break;
					q.add(mvNum);
				}
				
			}
		}
		
		System.out.println(v[target]);

	}

}