[BFS][Java][BOJ] #1697. 숨바꼭질

#BFS #너비우선탐색  #Silver1

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

🌷 문제 설명

✏️ 백준 연습문제: #1697. 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

⌨️ 입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

🖨️ 출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

입출력 예

입력	출력
5 17	4

💡 해결 포인트

1.  BFS
- Queue
- 수빈이와 동생이 처음에 같은 자리에 있을 경우
- 방문 체크(visited[])외 시간을 나타내는 배열(time[])로 카운트

 

 

 

🌷 내 코드

1.  BFS

import java.util.*;
import java.io.*;

public class BOJ_1697 {
    public static void main(String[] args) throws IOException { 
      System.setIn(new FileInputStream("example.txt"));
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      // 첫 번째 줄 입력
      String[] firstLine = br.readLine().split(" ");
      int N = Integer.parseInt(firstLine[0]); // 수빈이의 위치 
      int K = Integer.parseInt(firstLine[1]); // 동생의 위치

      // BFS
      boolean [] visited = new boolean[100001];
      Queue<Integer> queue = new LinkedList<>();
      int [] time = new int[100001];

      if (N == K) {
        System.out.println(0);
      }

      queue.add(N); // 수빈의 위치를 큐에 넣음
      visited[N] = true; // 방문 표시

      while (!queue.isEmpty()) { // 큐가 차 있으면
        int current = queue.poll(); // 수빈이의 현재 위치
        visited[current] = true; // 방문했다고 표시

        for (int next : new int [] {current + 1, current -1, current * 2}) { // 다음 위치
          if ( next >= 0 && next <= 100000 && !visited[next]) { // 범위 내에 있고 방문하지 않았다면
            queue.add(next); // 다음 큐에 넣음
            visited[next] = true; // 방문했다고 표시
            time[next] = time[current] + 1; // 시간 증가

            if (next == K) { // 동생 찾았으면
              System.out.println(time[next]); // 시간 출력
              break;
            }

          }
        }
        }
      }

    }

 

 

🌷 코멘트

알듯..말듯..ㅠ 대충 다 베껴서 써놓고 집와서 다시 풀어봤는데도 한참을 헤맸다 시간 배열과 방문 배열이 직관적으로 잘 와닿지 않아서 더 헷갈렸던거 같다. 

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com