5014_스타트링크

사용 알고리즘: bfs, dp

사용 언어: java

 

package week21;

import java.util.*;
import java.io.*;

public class Main_bj_5014_스타트링크 {
	static int 총층수, start, goal, 위로, 아래로;
	static int[] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		총층수 = sc.nextInt();
		start = sc.nextInt();
		goal = sc.nextInt();
		위로 = sc.nextInt();
		아래로 = sc.nextInt();
		
		dp = new int[총층수+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[start] = 0;
		
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {start, 0});
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			int up = cur[0] + 위로 <= 총층수 ?  cur[0] + 위로 : -1;
			int down = cur[0] - 아래로 >= 1 ?  cur[0] - 아래로 : -1;
			
			if(up > 0 && dp[up] > cur[1] + 1) {
				dp[up] = cur[1] + 1;
				q.add(new int[] {up, cur[1] + 1});
			}
			if(down > 0 && dp[down] > cur[1] + 1) {
				dp[down] = cur[1] + 1;
				q.add(new int[] {down, cur[1] + 1});
			}
		}
		
		if(dp[goal] != Integer.MAX_VALUE) System.out.println(dp[goal]);
		else System.out.println("use the stairs");
	}

}

 

 

까로 꼬롬~~~~

백준의

DFS+BFS 필수 문제

다 풀ㄹ었다!