[#알고리즘/BFS/[백준]5014번: 스타트링크(java)]

📘 Question

💡 Solution

S층에서 G층으로 가는 최단 경로를 찾는 문제로, 범위가 넓어 BFS를 사용하여 해결하였다. count 배열엔 해당 층으로 가기 위한 버튼 클릭 수를 저장한다.

출발하는 층(시작점)부터 큐에 넣어 위로 혹은 아래로 이동한 층을 다시 큐에 넣어가며 탐색한다. 이때, F층보다 높거나 1층보다 낮으면 패스한다. 탐색 과정에서 s == G 목적지를 만나게 되면 count 배열에 저장된 버튼 클릭 수를 출력한다. 만일 목적지를 만나지 못하고 bfs 함수가 종료될 경우엔 "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 BOJ_5014 {
	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];
		bfs(S);
		
		
	}
	
	public static void bfs(int s) {
		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];
				
				// 위 혹은 아래로 이동한 층이 F층보다 높거나 1층보다 낮으면 무시
				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");
	}
		
}

주의하자 !

어느 위치(cur)로 갔을 때, 몇 번 만에 갔는지를 기록하여 (distance[] 배열) 무한 루프로 빠지지 않게 하는 것.