[BOJ] 1697.숨바꼭질(BFS).java

#. Problem

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

* 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

이 문제도 결국 가장 빠른 시간을 구해야 하므로

BFS를 사용해야 한다.

이동할 수 있는 X-1, X+1, X*2 좌표로 차근차근 이동해보면서

동생을 찾았을 때, 종료해주면 된다.

#. Code

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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ1697 {       static int dx[] = { -1, 1 };     static int N, K, max = 100000;     static boolean visited[];       static class info {         int pos;         int time;           public info(int pos, int time) {             this.pos = pos;             this.time = time;         }     }       public static int bfs() {         // 동일한 지점에서 시작했다면         if(N == K) return 0;         int xx;         Queue<info> q = new LinkedList<>();         // 시작점         q.add(new info(N, 0));         visited[N] = true;                  while (!q.isEmpty()) {             info now = q.poll();             // -1 or +1 or x2 로 이동             for (int i = 0; i < 3; i++) {                 if(i==2) xx = now.pos * 2;    // 순간이동                 else xx = now.pos + dx[i];                 // 다음 지점이 동생이 있는 곳이라면                 // 현재 시간 + 1 을 return                  if(xx == K) return now.time + 1;                 // 범위를 초과하거나, 왔던 곳이면 pass                 if (xx < 0 || xx > max || visited[xx]) continue;                 q.add(new info(xx, now.time + 1));                 visited[xx] = true;             }         }         return 0;     }          public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine(), " ");           N = Integer.parseInt(st.nextToken());         K = Integer.parseInt(st.nextToken());                  visited = new boolean[max+1];         System.out.println(bfs());     }   }   Colored by Color Scripter

cs