[백준] 5014 스타트링크

www.acmicpc.net/problem/5014

5014번: 스타트링크

2020-11-16

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main5014 {
	public static int F, S, G, U, D, answer;
	public static int dx[];
	public static Queue<Integer> q;
	public static boolean vtd[];
	
	public static void solve() {
		int count = 0;
		boolean flag = false;
		loop:while(!q.isEmpty()) {
			int size = q.size();
			while(size > 0) {
				int x = q.poll();
				for(int i = 0; i < dx.length; i++) {
					int nx = x + dx[i];
					if(nx > F || nx <= 0) continue;
					if(nx == G) {
						flag = true;
						break;
					} else if(!vtd[nx]) {
						q.add(nx);
					} 
					vtd[nx] = true;
				}
				size--;
			}
			count++;
			if(flag) {
				answer = count;
				break loop;
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		F = sc.nextInt();
		S = sc.nextInt();
		G = sc.nextInt();
		U = sc.nextInt();
		D = sc.nextInt();
		
		q = new LinkedList<Integer>();
		vtd = new boolean[1000001];
		answer = 987654321;
		vtd[S] = true;
		dx = new int[2];
		
		dx[0] = U;
		dx[1] = -D;
		q.add(S);

		if(S == G) answer = 0;
		else solve();
		if(answer == 987654321) System.out.println("use the stairs");
		else System.out.println(answer);
	}
}

 

 

숨바꼭질을 풀어본 김에 비슷한 문제를 하나 더 풀어보았다. 

 

두 문제가 너무 유사해서 아주 사소한 부분만 다르게 풀어보았다. 숨바꼭질은 queue를 2차원 배열로 관리를 했지만, 사실 굳이 그럴 필요가 없다. 그래서 이 문제에서는 Integer로 관리했다.

 

대신 queue를 돌 때 마다 size를 체크해서 size만큼만 돌게 하며, 그 안에서 오르락 내리락 하는 것은 같은 count라고 보았다. 그리고 엘레베이터가 스타트링크(G)층에 도착하게 되면, count가 답이 된다. 숨바꼭질에서 2차원 배열 두 번째 값을 쓰는 것과 같은 원리이다.

 

만약 답이 초기값과 동일하게 나온다면 스타트링크(G)층에 도착하지 못한 것이므로, "use the stairs"문구를 출력한다.

---

void2017.tistory.com/115

[백준] 1697 숨바꼭질