[BOJ] 5014. 스타트링크(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

그냥 단순하게 생각하면

위로 올라갔다가 내려왔다가 하면서

도착 층으로 이동하는 문제다.

#. Code: Naive

먼저 시작은 단순하게 시작해보았다.

정말 단순하게.. 

올라갈 수 있을 때까지 올라갔다가

내려갈 수 있을 때까지 내려가면서

도착 층에 도달하나아가는 방식이다.

근데 BFS로 해결한 방법보다는 높은 속도를 보였다..!

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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ5014 {       static int F, S, G, U, D, cnt = 0;     static boolean isArrive;       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()); // up         D = Integer.parseInt(st.nextToken()); // down           isArrive = true;           if (S > G) {             // 회사가 나보다 낮을 층에 있을 때, 계속 내려가보자.             while (S > G) {                 Down();                 if(!isArrive) break;             }             // 더 내려왔다면 다시 올라가자.             while (S < G) {                 Up();                 if(!isArrive) break;             }             // 같은 층에 도착하지 못했다면              if (S != G) isArrive = false;         }          else if (S < G) {             // 회사가 나보다 높은 층에 있을 때, 계속 올라가보자.             while(S < G) {                 Up();                 if(!isArrive) break;             }             // 더 올라갔다면 다시 내려가자.             while(S > G) {                 Down();                 if(!isArrive) break;             }             // 같은 층에 도착하지 못했다면              if (S != G) isArrive = false;         }                  // 처음부터 같은 층일 경우, 바로 여기로 넘어오겠지         if(isArrive) System.out.println(cnt);         else System.out.println("use the stairs");     }       public static void Up() {         if(U == 0) {             isArrive = false;             return;         }         S += U;         cnt++;     }       public static void Down() {         if(D== 0) {             isArrive = false;             return;         }         S -= D;         cnt++;     }   }   Colored by Color Scripter

cs

#. Code: BFS

나이브하게 짜보고 다시 BFS로 해결해보았다.

갈 수 있는 층으로 조금씩 다 가보면서 dist[]에 버튼을 누른 수를 저장해두었다.

최고 층을 넘어가거나 1층 보다 내려갈 경우, 혹은 이미 방문한 층을 또 방문할 경우를 처리해주면서

도착 층에 도착하면 지금까지 누른 버튼 수를 res에 저장해주었다.

처음에 현재 층과 도착 층이 같은지 비교하는 코드를

다음 층으로 넘어가는 과정에서 수행하였는데,(line 44. 지점)

이 경우 입력부터 이미 시작점과 도착점이 같은 경우를 처리해주지 못 했었다.

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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ5014_bfs {       static int F, S, G, U, D;     static int max = 1000001;       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()); // up         D = Integer.parseInt(st.nextToken()); // down           int res = -1;         int[] button = {U, -D};         int[] dist = new int[max];         // 방문 확인을 위해 -1 로 초기화         Arrays.fill(dist, -1);         Queue<Integer> q = new LinkedList<Integer>();         // 강호의 위치에서 시작         dist[S] = 0;         q.add(S);         while(!q.isEmpty()) {             int now = q.poll();             // 회사 층 도착 혹은             // 시작층과 도착층이 같을 경우             if(now == G) {                 res = dist[now];                 break;             }             for (int i = 0; i < 2; i++) {                 int next = now + button[i];                 // 최고층을 넘어가거나 1층보다 내려가거나 이미 방문한 층이면 pass                 if(next > F || next < 1 || dist[next] >= 0) continue;                 // 아직 층에 도착하지 않았을 경우                 dist[next] = dist[now] + 1;                 q.add(next);             }         }         if(res == -1) System.out.println("use the stairs");         else System.out.println(res);     } } Colored by Color Scripter

cs