관리 메뉴

공부공간

BOJ - 5014 ) 스타트링크 본문

탐색 알고리즘/완전탐색(BFS,DFS)

BOJ - 5014 ) 스타트링크

SangwonSeo 개발자가될수있을까? 2021. 8. 21. 09:06
728x90


 

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

 

5014번: 스타트링크

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

www.acmicpc.net

 


총 F층짜리 건물에서 S층에서 시작해서 G층으로 가는데

한번의 이동에 +U / -D 만큼의 이동을 할 수 있다.

 

문제에서 적어도 몇번 가야하는지 물어보았기때문에, 최단거리문제와 동치이고 

BFS를 통하여 맨처음 도달했던 횟수를 구하면 출력해준다.

예외적으로 ( +U -D 했을 경우에 건물의 층수 범위를 넘어버린다던가 / 시작할때부터 S==G 인경우는 예외처리해주자 )

 

 

 


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

public class 스타트링크 {

	public static void main(String[] args) throws IOException {
		String stair = "use the stairs";
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int f = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		int g = Integer.parseInt(st.nextToken());
		int u = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		
		ArrayDeque<int []> dq = new ArrayDeque<>();
		// int [] = 0 번째에는 내위치, 1번째에는 횟수 
		boolean visit[] = new boolean[f+1];
		int answer = -1;
		visit[s] = true;
		dq.add(new int[] {s,0});
		while(!dq.isEmpty()) {
			int now[] = dq.poll();
			
			if(now[0]+u <= f && !visit[now[0]+u]) {
				if(now[0]+u==g) {
					answer = now[1]+1;
					break;
				}
				visit[now[0]+u] = true;
				dq.add(new int[] {now[0]+u, now[1]+1});
			} 
			
			if(now[0]-d >=1 && !visit[now[0]-d]) {
				if(now[0]-d==g) {
					answer = now[1]+1;
					break;
				}
				visit[now[0]-d] = true;
				dq.add(new int[] {now[0]-d, now[1]+1});
			}
		}
		if(s==g) answer= 0;
		System.out.println(answer == -1 ? stair : answer);
	}
}

728x90

'탐색 알고리즘 > 완전탐색(BFS,DFS)' 카테고리의 다른 글

BOJ - 1584 ) 게임  (0) 2021.10.17
BOJ - 5014 ) 스타트링크  (0) 2021.08.21
BOJ - 15812 ) 침략자 진아  (0) 2021.05.13
BOJ - 9205 ) 맥주 마시면서 걸어가기  (0) 2020.11.26
BOJ - 1939 ) 중량제한  (0) 2020.09.28
BOJ - 14889 ) 스타트와 링크  (0) 2020.09.08
0 Comments
댓글쓰기 폼