<Algorithm> 18. 1697번 숨바꼭질

1. 1697번 숨바꼭질

• BFS 문제, 깊이를 최소로 하는 문제이므로(최단거리) BFS의 깊이를 이용해서 풀이한다.

• 주의할점은 깊이 값을 모든 정점에 대해서 따로 배열을 만들어서 처리하여야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static boolean[] visited = new boolean[100001];
    static int[] dist = new int[100001];
    static ArrayList<Edge>[] graph = new ArrayList[100001];
    
    
    public static void main(String[] args) throws IOException {
        
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine());
         int[] input = new int[2];
         
         for(int i=0; i<2; i++) {
             input[i] = Integer.parseInt(st.nextToken());
         }
         bfs(input[0], input[1]);
    }    
    
    public static void bfs(int start_vertex,int K) {
        
        if(start_vertex == K) { // 같을 경우 0으로 처리
            System.out.println(0);
            return;
        }
        
        
        visited[start_vertex] = true; // 방문표시
        dist[start_vertex] = 0; // 걸린 시간
        
        Queue<Integer> queue = new LinkedList<Integer>(); 
        
        graph[start_vertex]=new ArrayList<Edge>(); 
    
            if(start_vertex+1 <= 100000) {
                graph[start_vertex].add(new Edge(start_vertex+1));
            }
            
            if(start_vertex-1 >= 0) {
                graph[start_vertex].add(new Edge(start_vertex-1));
            }
            
            if(start_vertex*2 <= 100000 && start_vertex*2 != 0) {
                graph[start_vertex].add(new Edge(start_vertex*2));
            }
            
         queue.add(start_vertex);
         
    while(!queue.isEmpty()) {
        
        int vertex = queue.remove();
    
          if(vertex != start_vertex) {
              graph[vertex]=new ArrayList<Edge>();
 
              if(vertex+1 <= 100000) {
                    graph[vertex].add(new Edge(vertex+1));
                }
                
                if(vertex-1 >= 0) {
                    graph[vertex].add(new Edge(vertex-1));
                }
                
                if(vertex*2 <= 100000) {
                    graph[vertex].add(new Edge(vertex*2));
                }
                // vertex 마다 간선을 생성한다
          }
          
          for(Edge e : graph[vertex]) {
              if(e.adj_vertex != K) {
                  if(!visited[e.adj_vertex]) {
                      visited[e.adj_vertex] = true; // 방문함
                      dist[e.adj_vertex] = dist[vertex] + 1; // 이전 vertex의 거리에서 +1
                      queue.add(e.adj_vertex);
                  }
              }else {
                  dist[e.adj_vertex] = dist[vertex]+1;
                  System.out.println(dist[e.adj_vertex]);
                  return;
              }
              
          }
          
        
        }        
    }
}
 
class Edge{
    int adj_vertex;
    public Edge(int adj_vertex) {
        this.adj_vertex = adj_vertex;
    }
    
}