[백준] 5014번 스타트링크

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q5014.java

1층 부터 시작되는 건물의 3개의 층의 위치가 주어진다. 이중 F층은 꼭대기 층이고,
S층은 현재 있는 층이며, G층은 도착해야할 층 수이다.
엘레베이터에는 2개의 버튼이 있다. U와 D 이 위로와 아래로 가는 버튼은 각 각 정해진 층수 만큼만
이동이 가능하다. 각 층의 위치 정봐와 U와 D의 이동 가능한 층수 정보가 주어졌을 때
S층에서 G층으로 갈 수 있으면 최소 누른 버튼 수를 갈 수 없다면 use the stairs를 출력하여라.

처음 생각

BFS 탐색을 통해 U와 D버튼을 눌렀을 경우 Queue에 넣어주면서 탐색을한다.

▶ U와 D버튼이 0일 수도 있기 때문에 0이 아니라면 넣어주어야한다. 0일경우 계속해서 Queue에 들어가기 때문이다.

다음 생각

위의 방식으로 하면 시간초과가 나오게된다. 

▶ 생각해보면 이유는 나름 간단하다. 반복작업이 많아지기 때문이다. 예를들어 1000층에 가야하고 U와 D가 각 1칸 씩이라고 생각하면 처음 queue에 S층을 넣어주고 위와 아래 1개씩 또 Queue에 넣어 준다. 그럼 아래로 들어간 Queue중 하나는 또 원래의 1000층으로 오게된다. 이러한 중복 작업때문에 Queue의 찾는 작업이 중단 될 때까지 계속적으로 2배의 정보들이 늘어나게된다.

다다음 생각

따라서 위와 같은 문제를 해결하기 위해 방문 배열을 만들어 이미 방문했던 층일 경우는 탐색을 하지 않도록 하였다.

▶ 이미 방문한곳은 어차피 이전에 했던 작업(U와 D)를 똑같이해서 나아가기 때문이다.

방안

1) 시간 초과가 나올경우 제거할 수 있는 탐색을 가지치기해줌으로서 문제를 해결 할 수 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

package baekjoon.q1000;   import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;   public class Q5014 {     static int[] arr,move;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         // F(0) S(1) G(2)         // 건물에서 가장 높은 층은 F층이다.         arr = new int[3];         for(int i=0;i<3;i++)             arr[i] = sc.nextInt();         // U(0) D(1)         move = new int[2];         move[0] = sc.nextInt();         move[1] = sc.nextInt();         visited = new boolean[arr[0]+1];         solve();     }          static boolean[] visited;         private static void solve() {         Queue<Pair> queue = new LinkedList<>();         queue.add(new Pair(arr[1], 0)); // S층 넣어주기         visited[arr[1]] = true;         boolean flag = false;         while(!queue.isEmpty()) {             Pair t = queue.poll();             // 도착 가능하면             if(t.n==arr[2]) {                 flag = true;                 System.out.println(t.cnt);                 break;             }                          // 위층 보내기 && 최상층 넘어가지 않으면 && 방문 한적 없으면             if(move[0]!=0&&t.n+move[0]<=arr[0]&&!visited[t.n+move[0]]) {                 visited[t.n+move[0]]=true;                 queue.add(new Pair(t.n+move[0], t.cnt+1));             }             // 아래층 보내기 && 최하층 밑으로 가지 않으면 && 방문 한적 없으면             if(move[1]!=0&&t.n-move[1]>0&&!visited[t.n-move[1]]) {                 visited[t.n-move[1]]=true;                 queue.add(new Pair(t.n-move[1], t.cnt+1));             }         }         if(!flag) System.out.println("use the stairs");     }          static class Pair{         int n,cnt;         Pair(int n,int cnt){             this.n= n;             this.cnt = cnt;         }     } }