https://www.acmicpc.net/problem/5014
문제
> 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다.
> 오늘은 강호의 면접날이다.
> 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.
> 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다.
> 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.
> 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다.
> U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다.
(만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)
> 강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.
> 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.접근
S층에서 목표하는 G층까지 가야한다. 이때, 갈 수 있는 방법은 U만큼 올라가는거, D만큼 내려가는것이다.
예를 들어 2층에서 5층가는데 U가 2고 D가 1이면 2->4->6->5로 가면 될것 같지만 존재하지 않는층은 갈 수 없다. 따라서 2->4->3->5이런식으로 가야한다.
그래서 역으로갈 생각을 했다. 미로도 도착지점에서 뻗어가면 쉽게 풀 수 있듯이 말이다.
반대로 가야하므로 U만큼 -, D만큼 + 해주면서 가야한다.
이제 시작은 G층이고 목표는 S층이다. 큐로 관리하며 큐에는 현재층, 이동 횟수를 가진다.
현재층을 가져와서 거기에 -U, +D 두 경우를 하는데 두 계산으로 새 층을 구했을 때, 범위를 넘어가지 않을 때만 따진다.
갔던 층에는 방문처리를 하여 무한루프를 피해준다. 또 방문이 됐다는건 최소값이 보장되지 않기 때문이다.
해당 조건을 만족하며 가능한 층을 while문으로 탐색하다 원하는 S층에 도달하면 이동횟수를 출력해준다.
만약 while문이 끝난다면 불가능하다는 뜻이므로 use the stairs를 출력한다.
문제해결
> F,S,G,U,D를 입력받고 방문처리 배열 visited를 선언한다.
> 처음부터 불가능한 경우, 내려가야하는데 D가 0, 올라가야하는데 U이 0인 경우를 처리해준다.
> 탐색 메서드 BFS로 현재 층, 이동횟수의 초기값을 넣고 호출한다.
> BFS 내부에서 큐를 사용하는데 큐의 타입으로 사용자 정의 해둔 Pair클래스를 사용한다.
> while문에서 큐의 맨 앞을 가져오고 first인 현재 위치가 목표인 S와 같은지 보고 맞으면 second를 출력한다.
> 아니라면 이동을 해야하므로 U를 뺀 값, D를 더한 값의 범위가 유효한지 보고 이동한다.
> 이동한 층스와 이동 횟수를 가지고 큐에 다시 넣으며 방문처리를 해준다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//5014 스타트링크
static int F, S, G, U, D;
static boolean[] visited;
static void BFS(int start, int rst) {
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(start, rst));
while(!q.isEmpty()) {
Pair pair = q.poll();
if(pair.first == S) {
System.out.println(pair.second);
return;
}
if(pair.first - U >= 1){
if(!visited[pair.first - U]) {
q.offer(new Pair(pair.first - U, pair.second + 1));
visited[pair.first - U] = true;
}
}
if(pair.first + D <= F) {
if(!visited[pair.first + D]) {
q.offer(new Pair(pair.first + D, pair.second + 1));
visited[pair.first + D] = true;
}
}
}
System.out.println("use the stairs");
}
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());
visited = new boolean[F+1];
if((G < S && D == 0) || (G > S && U == 0)) {
System.out.println("use the stairs");
return;
}
BFS(G, 0);
}
public static class Pair {
int first, second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
}
후기
시간초과가 날까 걱정했는데 안터져서 다행이었다. 아직도 시간복잡도의 개념이 얕다. 더 공부해보자.
