7-8. 송아지 찾기 (BFS)

---

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 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int hunsu = Integer.parseInt(st.nextToken());
		int sonage = Integer.parseInt(st.nextToken());

		Queue<Integer> q = new LinkedList<>();

		int[] visited = new int[10006];

		int result = 0;

		if (hunsu > sonage) {
			result = hunsu - sonage;
		} else {

			q.offer(hunsu);

		}

		while (!q.isEmpty()) {
			int point = q.poll();
		//	System.out.println(point);
			if (point == sonage) {
				result = visited[point];
				break;
			}
			if (point > 0 && point < 10001) {
				
			if(sonage>=point+5) {

				q.offer(point + 5);
				visited[point + 5] = visited[point] + 1;
			}else if(sonage>point) {

				q.offer(point + 1);
				visited[point + 1] = visited[point] + 1;
			}else{
				q.offer(point - 1);
				visited[point - 1] = visited[point] + 1;
			}
			
	


			}
		}

		System.out.println(result);

	}

}

 

최소 이동횟수를 구하기 위해 방문여부를 int 로 주었다.

뒤로 이동하는 경우는 -1 밖에 없기 때문에 송아지보다 현수가 클경우 그냥 현수-송아지 로 했다.

 

처음에는 앞으로 이동할때 +1 과 +5를 같이 넣어줬지만 멀리 있을 경우 해당 로직이 매우 오래걸리게 되어 +5보다 같거나 

 

 

 

 

 

 

import java.util.Scanner;

public class Main {

	static int movePoint[] = { 1, -1, 5 };
	static int res = Integer.MAX_VALUE;
	static boolean visit[] = new boolean[10006];

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		

		int start = sc.nextInt();
		int end = sc.nextInt();
	

		findCalves(end, start, 0);

		System.err.println(res);
	}// end main

	private static void findCalves(int end, int curPoint, int cnt) {

		int funCurPoint = curPoint;
	//	System.err.println("funCurPoint: " + funCurPoint + "/ end: " + end + "/ cnt: " + cnt);
		// 종료조건
		if (funCurPoint == end) {
	//		System.err.println("hiiiiiiiiiiii");
			if (res > cnt) {
				res = cnt;
		//		System.err.println("res2: " + res);
			}
			return;
		}
		if ((funCurPoint >= 1 || funCurPoint <= 10000)) {

			if (funCurPoint + 5 <= end && visit[funCurPoint] == false) {
				visit[funCurPoint] = true;
				funCurPoint = funCurPoint + 5;
				cnt++;
				findCalves(end, funCurPoint, cnt);
			} else if (funCurPoint > end && visit[funCurPoint] == false) {
				visit[funCurPoint] = true;
				funCurPoint--;
				cnt++;
				findCalves(end, funCurPoint, cnt);
			} else if (funCurPoint < end && visit[funCurPoint] == false) {
				visit[funCurPoint] = true;
				funCurPoint++;
				cnt++;
				findCalves(end, funCurPoint, cnt);
			}

		//	System.err.println("funCurPoint:: " + funCurPoint);

		}
		

	}// end findCalves
}

재귀로도 풀어보았다.