백준 5014 - 스타트링크

Java

5014 번 - 스타트링크

문제

접근 방법

한 점에서, 다른 한 점으로 갈 수 있는 최단 거리를 구하는 문제이다.

BFS는 한 점에 처음 도달하면, 그 위치까지 도달하는데 걸린 횟수가 최소인 최단거리이므로 이를 응용한다.

시작 점에서, 주어진 크기만큼의 상 / 하를 이동하며 방문할 때마다 queue에 넣고 방문하였다 표시한다. 이후 목표 층에 도달하면 그 위치가 최단 거리이므로, 그 횟수를 결과에 저장하고 BFS를 종료한다.

코드

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

public class Main {
	static int f,s,g,u,d, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	f = stoi(stk.nextToken());	// 총 층수
    	s = stoi(stk.nextToken());	// 현재 있는 곳
    	g = stoi(stk.nextToken());	// 목표
    	u = stoi(stk.nextToken());	// 한번에 위로 갈 수 있는 개수
    	d = stoi(stk.nextToken());	// 한번에 밑으로 갈 수 있는 개수

    	boolean[] vis = new boolean[f + 1];
    	boolean isOk = false;
    	Queue<int[]> queue = new LinkedList<int[]>();
    	queue.add(new int[] {s,0});
    	vis[s] = true;

    	int curN, cnt, nextN;

    	int[] q;
    	while(!queue.isEmpty()) {
    		q = queue.poll();

    		curN = q[0];
    		cnt = q[1];

    		if(curN == g) {
    			result = cnt;
    			isOk = true;;
    			break;
    		}
    		// 올라갈 수 있는지 체크
    		nextN = curN + u;
			// 범위를 벗어나지 않았으며, 처음 방문한 장소이면
    		if(isIn(nextN) && !vis[nextN]) {
    			queue.add(new int[] {nextN, cnt + 1});
    			vis[nextN] = true;
    		}

    		// 내려갈 수 있는지 체크
    		nextN = curN - d;
    		if(isIn(nextN) && !vis[nextN]) {
    			queue.add(new int[] {nextN, cnt + 1});
    			vis[nextN] = true;
    		}
    	}

    	if(isOk)
    		System.out.println(result);
    	else
    		System.out.println("use the stairs");

    	br.close();
	}

	static boolean isIn(int num) {
		if(1 <= num && num <= f)
			return true;
		return false;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점