백준 5014번 : 스타트링크

 문제

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

5014번: 스타트링크

55014 스타트링크

 

 구현 방법

처음 강호가 있는 층에서 갈 수 있는 방향은 위, 아래 두 가지 입니다.
이동한 층에 따라 다음 이동할 층수가 주어지기 때문에 너비 우선 탐색을 사용하여 풀어주었습니다.

visit 배열을 사용하여 방문체크를 해주고 따로 이동 횟수를 카운트 할 수도 있지만

저는 visit 배열을 int형으로 선언해 -1로 채워놓고 이동 횟수를 저장하였습니다.

주의할 점은 

1. 해당 층에 서 있을수도 있으므로 0이 출력될 수 있습니다.

2. 스타트링크 층수가 끝 층일수도 있으므로 배열의 범위를 F가 아닌 F+1로 선언해야 합니다.

3. 1층 아래, F층 위에는 갈 수 없으므로 조건을 추가해줘야 합니다.

 

 구현 코드

package BOJ.Gold;

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

public class Bㅒㅓ5014_스타트링크 {
	static int F, S, G, U, D;
	static int[] visit;
	static Queue<Integer> queue;
	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());
		U = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		visit = new int[F+1];
		queue = new LinkedList<>();
		queue.offer(S);
		Arrays.fill(visit, -1);
		visit[S] = 0;
		System.out.println(bfs());
	}
	
	static String bfs() {
		while(!queue.isEmpty()) {
			int size = queue.size();
			for (int s=0;s<size;s++) {
				int now = queue.poll();
				if (now==G) return(visit[now]+""); // 스타트링크 층수에 도착하면 끝!
				bfsInput(now, now+U);
				bfsInput(now, now-D);
			}
		}
		return "use the stairs";
	}
	
	static void bfsInput(int now, int next) {
		if (next>0 && next<=F && visit[next]==-1) {
			queue.offer(next);
			visit[next] = visit[now]+1;
		}
	}
}

 

정답!