알고리즘 스터디 (숨바꼭질[백준 1697])

박윤택·2022년 6월 14일
2

알고리즘

목록 보기
14/25

문제

숨바꼭질(Silver 1) - 1697


문제 이해

  • N과 K를 입력받아서 N에서 K로 이동해야한다.
  • 이동방식은 3가지 현재 위치-1, 현재 위치+1, 현재위치*2
  • 가장 빠른 시간 출력

현재 위치를 기준으로 이동방식 3가지를 조합하여 BFS를 이용하여 K로까지 걸린 시간을 구한다.


코드

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

public class HidePlay {
  /* baekjoon 1697 */

  // 위치를 담을 수 있는 객체
  public static class Location {
    int time; // 얼마나 걸렸는지
    int position; // 현재 위치

    Location(int time, int position) {
      this.time = time;
      this.position = position;
    }
  }

  static int N;
  static int K;
  static Queue<Location> queue; // 다음에 방문할 곳 저장
  static boolean[] visited; // 방문했는지 확인

  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());
    queue = new LinkedList<>();
    visited = new boolean[100001]; // 0<= K <= 100000이므로 1만 더 크게 설정 
    bfs();

    // Runtime.getRuntime().gc();
    // long usedMemory = Runtime.getRuntime().totalMemory() -
    // Runtime.getRuntime().freeMemory();
    // System.out.print(usedMemory + " bytes");
  }

  public static void bfs() {
    queue.add(new Location(0, N)); // 초기위치 Queue에 넣기
    visited[N] = true; // 현재 위치 방문했다고 표시
    while (!queue.isEmpty()) {
      Location current = queue.poll();
      
      // 현재 위치가 K이면 종료
      if (current.position == K) { 
        System.out.println(current.time);
        return;
      }
      
      // 현재위치-1 로 이동할때
      if (0 <= current.position - 1 && !visited[current.position - 1]) {
        queue.add(new Location(current.time + 1, current.position - 1));
        visited[current.position - 1] = true;
      }
      
      // 현재위치+1 로 이동할때
      if (current.position + 1 < visited.length && !visited[current.position + 1]) {
        queue.add(new Location(current.time + 1, current.position + 1));
        visited[current.position + 1] = true;
      }
      
      // 현재위치*2 로 이동할때
      if (current.position * 2 < visited.length && !visited[current.position * 2]) {
        queue.add(new Location(current.time + 1, current.position * 2));
        visited[current.position * 2] = true;
      }
    }
  }

}

코드 설명

  1. N과 K를 입력 받는다.
  2. Queue를 초기화하고 방문했는지 확인하는 배열을 선언한다.
  3. BFS 함수를 이용한다.
    3-1. 초기위치를 Queue에 넣고 현재 값을 index로 하는 배열의 요소를 true로 바꾼다. 즉 방문을 표시한다.
    3-2. Queue가 빌때까지 반복한다.
    3-3. Queue에서 하나를 빼서 현재값이 K인지 확인한다. K이라면 현재 위치까지 걸린 시간을 출력하고 종료한다.
    3-4. 현재위치-1를 다음 방문할 위치로 인식하고 Queue에 넣고 방문여부를 확인한다.
    3-5. 현재위치+1를 다음 방문할 위치로 인식하고 Queue에 넣고 방문여부를 확인한다.
    3-6. 현재위치*2를 다음 방문할 위치로 인식하고 Queue에 넣고 방문여부를 확인한다.


0개의 댓글