[Java] baekjoon_1697 : 숨바꼭질

그래프 이론, 그래프 탐색, 너비 우선 탐색

숨바꼭질 : Silver1

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

1697번: 숨바꼭질

 

 

풀이

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

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  public static void main(String[] args) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    bw.write(bfs(N, K) + "\n");
    bw.flush();
    br.close();
    bw.close();
  }

  private static int bfs(int N, int K) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[100001];
    int[] time = new int[100001];

    queue.offer(N);
    visited[N] = true;
    time[N] = 0;

    while (!queue.isEmpty()) {
      int current = queue.poll();

      if (current == K) {
        return time[current];
      }

      if (current - 1 >= 0 && !visited[current - 1]) {
        queue.offer(current - 1);
        visited[current - 1] = true;
        time[current - 1] = time[current] + 1;
      }
      if (current + 1 <= 100000 && !visited[current + 1]) {
        queue.offer(current + 1);
        visited[current + 1] = true;
        time[current + 1] = time[current] + 1;
      }
      if (current * 2 <= 100000 && !visited[current * 2]) {
        queue.offer(current * 2);
        visited[current * 2] = true;
        time[current * 2] = time[current] + 1;
      }
    }

    return -1; // 동생을 찾지 못한 경우
  }
}

 

 

 

ㄴ queue와 visited 배열, time배열을 이용해서 BFS 알고리즘에 필요한 큐와 방문 여부를 나타내는 배열, 그리고 각 위치까지의 시간을 나타내는 배열을 선언했다.
ㄴ queue.offer(N), visited[N] = true, time[N] = 0은 초기 위치인 N을 큐에 추가하고, 해당 위치를 방문했음을 표시하고, 해당 위치까지의 시간을 0으로 설정했다.
ㄴ while (!queue.isEmpty()) { ... }을 통해 큐가 비어있지 않은 동안에 반복한다. (큐에는 탐색해야 할 위치들이 저장되어 있다.)
ㄴ int current = queue.poll(); 큐에서 현재 위치를 가져와서, 이 위치부터 인접한 위치들을 탐색하도록 한다.
ㄴ if (current == K) { return time[current]; }는 현재 위치가 동생의 위치인 경우에는 해당 위치까지의 시간을 반환하고 종료하도록 했다.
ㄴ 그 외의 경우에는 현재 위치에서 -1, +1, 2배 위치로 이동할 수 있는지 확인하고, 방문한 적이 없는 위치인 경우에만 큐에 추가하여 탐색을 진행했다.
ㄴ 마지막으로 동생의 위치에 도착하지 못한 경우에는 -1을 반환하도록 했다.

너비 우선 탐색(BFS)

BFS는 그래프나 트리에서 최단 경로를 찾는 알고리즘 중 하나이다.
이 알고리즘은 시작 정점으로부터 가까운 정점부터 탐색하는 방식으로 동작한다.
BFS는 큐(Queue)를 사용하여 구현된다.

 

 

visited 배열

방문 여부 배열은 각 정점이 이미 방문되었는지 여부를 나타내는 배열이다.
이 배열은 중복 방문을 방지한다.

 

time 배열

시간 배열은 각 정점까지의 최단 시간을 저장하는 배열이다.
시작 위치부터 각 위치까지의 최단 이동 시간을 계산하여 저장한다.

 

Queue와 초기화

BFS 알고리즘을 사용하기 위해 Queue를 사용했다. (Java에서는 LinkedList 클래스를 활용하여 Queue를 구현한다.)
방문 여부를 나타내는 visited 배열과 최단 시간을 나타내는 time 배열을 초기화한다.

 

시작 위치 추가

시작 위치인 N을 큐에 추가하고, 방문 여부를 true로 설정하며, 해당 위치까지의 최단 시간을 0으로 설정했다.

 

탐색

1. 큐가 빌 때까지 반복한다. 큐에는 탐색해야 할 위치들이 저장되어 있다.
2. 큐에서 현재 위치를 가져온다.
3. 현재 위치가 동생의 위치인 경우에는 해당 위치까지의 최단 시간을 반환하고 종료한다.
4. 그렇지 않은 경우에는 현재 위치에서 인접한 위치들을 탐색한다. (- 1, + 1, * 2)
5. 각 인접한 위치에 대해 방문 여부를 확인하고, 방문한 적이 없는 경우에만 큐에 추가하여 탐색을 계속한다.

 

종료

동생의 위치에 도착하지 못한 경우에는 -1을 반환한다.