[백준] 5014번 : 스타트링크 - JAVA [자바]

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

5014번: 스타트링크

문제

 

이 문제는 BFS로 쉽게? 풀었다. 

로직은 아래와 같다.

1. Route 클래스를 저장하는 Queue를 생성한다.

2. Queue에 초기값인 현재층수와 버튼을 누룬횟수인 0을 넣는다.

3. BFS을 돌면서 아래의 조건을 만족하면 Queue에 다음층을 넣는다.

• 다음 층이 F층 위에 있거나, 1층 밑이면 Continue
• 다음 층이 만약 방문한 층이면 Continue
• 다음 층이 만약 목적지에 도착한다면 Return

구현도 딱히 어려운것이 없었지만 30%쯤에 틀렸다고 나온다...... ㅋㅋ

그 이유는 현재 위치와 목적지 위치가 같으면 버튼을 누른 횟수가 0으로 바로 종료가 되어야 했지만  BFS 로직을 돌아갔기 때문이다.

진짜.... 문제를 잘 읽고, 코딩테스트를 볼때 테스트케이스를 조금더 생각해서 작성을 해야겠다고 느꼈다. (이게 제일 어려움)

---

전체 코드

public class Main {
	static int F, S, G, U, D;
	static int[] dir;
	public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("input.txt"));
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	
    	st = new StringTokenizer(in.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());
    	
    	dir = new int[2];
    	dir[0] = U;
    	dir[1] = -D;
    	
    	// 만약 출발한 층이 목적지이면 바로 BFS을 돌지 않는다. 
    	if(S == G) {
    		System.out.println(0);
    	}
    	else {
    		bfs();	
    	}
    }
	
	static void bfs() {
		Queue<Route> queue = new ArrayDeque<>();
		boolean[] visit = new boolean[2010000];
		
		queue.offer(new Route(S, 0));
		visit[S] = true;
		
		while(!queue.isEmpty()) {
			Route cur = queue.poll();
			
			for(int i = 0; i < 2; i++) {
				int next = cur.floor + dir[i];
				
				// 1. 만약 F층 위에 있거나 1층 밑이면 다음
				if(next > F || next < 1) continue;
				
				// 2. 만약 방문한 층이면 다음 
				if(visit[next]) continue;
				
				// 3. 만약 목적지에 도착하면 종료;
				if(next == G) {
					System.out.println(cur.cnt + 1);
					return;
				}
				
				queue.offer(new Route(next, cur.cnt + 1));
				visit[next] = true;
			}
		}
		
		System.out.println("use the stairs");
	}
}

---

결과