[백준] 5014 스타트링크

1. 문제

www.acmicpc.net/problem/5014

5014번: 스타트링크

2. 접근방법

너비를 넓혀 가며 탐색하는

bfs 중 가장 기초적인 형태의 문제

 

현재 위치에서 시작해서

위로 가는 것과 아래로 가는 것 두가지 분기로 나누어

넓혀 나가며 탐색하면 된다.

 

이미 도착한 장소는 그 후에 도착하는 것은 의미가 없으니

visit처리로 다시 방문 못하게 해주면 된다.

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class G5_5014스타트링크 {
	public static void main(String[] args) throws Exception {
		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()); // 아래
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(S);
		boolean visit[] = new boolean[F + 1];
		visit[S] = true;
		int cnt = 0;
		boolean flag = false;
		gg:while (!que.isEmpty()) {
			int size = que.size();
			for (int i = 0; i < size; i++) {
				int now = que.poll();
				if (now == G) {
					flag = true;
					break gg;
				}
				int up = now + U;
				if (up <= F  && !visit[up]) {
					visit[up] = true;
					que.offer(up);
				}
				int down = now - D;
				if ( down > 0 && !visit[down]) {
					visit[down] = true;
					que.offer(down);
				}
			}
			cnt++;
		}

		System.out.println(flag? cnt:"use the stairs");

	}

}

4. 마치며

별로 어렵지 않다