[백준 5014번 / 스타트링크 / JAVA / BFS]

 

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

5014번: 스타트링크

 

문제 접근

모든 층을 탐색하는 건 쉽게 나왔으나 목표층을 방문하지 못할 시 실패 문구를 뜨게하는 조건이 문제였다.

UP, DOWN으로 모든 층을 탐색하고 도달하지 못하게 될 경우 반복문을 나와서 출력해주자라곤 생각했으나 쉽지 않았다.

핵심은 큐를 사용해 탐색할 층을 넣어두는 것, 더 이상에 큐에 값이 없단 건 새로 방문할 층이 없단 것

while문을 돌면서 계속 큐에 값을 삽입하고 층 탐색 시 값을 꺼낸다.

 

방문했던 층과 움직인 횟수는 배열로 생성해서 체크

→ 2층(인덱스2)에서 시작 후 1씩 위 아래로 움직였다면 인덱스1과 인덱스 3의 움직인 횟수는 1이 되는 것 

 

요즘 드는 생각인데 그림으로 잘 설명해주거나 설명이 짧고 간결하게 표현된 게 아니라면 그냥 직접 코드보면서 해석하는게 더 이해하는데 도움되더라..

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

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 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());
		
		int[] count = new int[F+1]; // 움직임 횟수 확인 용도
		
		Queue<Integer> q = new LinkedList<>();
		boolean[] check = new boolean[F+1];
		
		q.add(S);
		check[S] = true; // 방문한 층 확인 용도
		count[S] = 0;
		
		// 해당 반복문 내에서 계속 큐를 삽입, 꺼내는 작업이 진행된다. → 모든 층 탐색
		while(!q.isEmpty()) { // 모든 층을 방문했거나 목표층 도달 시 탈출
			
			int pull = q.poll(); // 가장 오래 저장된 큐 값 꺼내기
			
			if(pull == G) { // 목표층 도달
				System.out.println(count[pull]);
				return;
			}
			
			for(int i=0; i<2; i++) {
				
				int next = 0; // 현재 층에서 증가했을 대와 감소했을 때 탐색
				if(i==0) next = pull + U; 
				else next = pull - D; 
				
				if(next > F || next < 1) continue; // 층 범위를 벗어나면
				
				if(!check[next]) { // 방문하지 않은 층일 경우
					check[next] = true; 
					q.add(next); // 해당 층을 방문하기 위해 큐에 값 넣기
					count[next] = count[pull] +1; 
				}
			}
		}
		System.out.println("use the stairs");
	}
}