[BaekJoon 5014번 / JAVA] 스타트링크

Question

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

5014번: 스타트링크

 

---

💡 Solution

BFS 유형의 문제로, 가장 먼저 출발하는 층(S)을 큐에 넣고, 해당 층을 기준으로 위로 혹은 아래로 이동합니다. 그럼 이동한 층을 다시 큐에 넣어 위로 혹은 아래로 탐색하는 과정을 반복합니다.

 

이때, 이동한 층이 F층보다 높거나 1층보다 낮으면 패스합니다. 만일 큐가 빌 때까지 목적지를 만나지 못하고 종료될 경우엔 "use the stairs"를 출력합니다.

 

유의할 점은, 이미 방문했던 층을 다시 방문하는 일이 없도록(즉, 무한루프가 발생하지 않도록) visited 배열을 사용해 방문한 층을 체크해줍니다.

 

💻 Code

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 BJ5014 {
	static int F, S, G, U, D;
	static int[] dir = new int[2];
	static int[] count;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		F = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		G = Integer.parseInt(st.nextToken());
		dir[0] = Integer.parseInt(st.nextToken());
		dir[1] = -Integer.parseInt(st.nextToken());
        
		count = new int[F + 1];
		solve();
	}
	
	public static void solve() {
		boolean[] visited = new boolean[F + 1];
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(S);
		visited[S] = true;
		count[S] = 0;
		
		while (queue.size() != 0) {
			int now = queue.poll();
			if (now == G) {
				System.out.println(count[now]);
				return;
			}
			
			for (int i = 0; i < 2; i++) {
				int next = now + dir[i];
				if (next > F || next < 1) {
					continue;
				}
				if (!visited[next]) {
					visited[next] = true;
					queue.add(next);
					count[next] = count[now] + 1;
				}
			}
		}
		System.out.println("use the stairs");
	}

}