[문제 풀이] 백준 1697번 숨바꼭질 JAVA

문제

 

  문제접근 방법   

해당 문제는 동생이 위치해 있는 값과 수빈이가 위치해 있는 값이 주어질 때 수빈이가 걷거나 순간이동해 동생의 위치에 도달할 수 있는 최소 시간을 구하는 프로그램을 작성하는 문제로 걷는다면 수빈이 위치가 X일 때 X+1, X-1이 가능하고 순간이동한다면 2*X가 가능하다.

처음에는 문제 접근이 어려웠다. bfs나 dfs문제 모두 처음 접했던 문제가 2차원에서 접근하거나 배열을 통한 접근으로 문제를 풀이했었는데 단순 값들만 주어지고 최소 시간을 구하려니 방문처리는 어떤식으로 해야 하지? BFS로 푸는 문제가 맞나? 이런 의문이 들었었다. 하지만 결국 배열이 존재하든 안 하든 BFS는 탐색을 통해 최단 경로를 구할 수 있는 알고리즘이고 이를 이해하고는 어렵지 않게 문제 풀이가 가능했다. 

 

 

< 초기 코드 >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static int second;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int k=s.nextInt();
        
        visited=new boolean[k+1];
        
        dfs(n,k,0);
        System.out.print(second-1);
    }
    public static void dfs(int n,int k,int sec){
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{n,sec});
        visited[n]=true;
        while(!q.isEmpty()){
            int loc[]=q.poll();
            if(loc[0]==k){second=loc[1];break;}
            int move[]={loc[0]-1,loc[0]+1,loc[0]*2};
            
            for(int i=0;i<3;i++){
                if(move[i]>=n&&move[i]<=k&&!visited[move[i]]){
                    visited[move[i]]=true;
                    q.offer(new int[]{move[i],loc[1]+1});
                }
            }
            
        }
    }
}

해당 문제는 상하좌우 이런식의 이동이 아닌 걷기와 순간이동이 가능하다. 그래서 k을 입력받아서 visited를 k만큼의 크기로만 초기화한다면 이는 모든 경우를 고려하지 못한 것이다. 예를 들어 k인데 순간이동하고 뒤로 걸었을 때가 최단 경로이면 이미  방문처리에서 인덱스 오류가 나게 된다. 그래서  문제에서 제시한 범위로 고쳐서 아래와 같이 작성하였다. 

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static int second;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int k=s.nextInt();
        
        visited=new boolean[100001];
        
        dfs(n,k,0);
        System.out.print(second);
    }
    public static void dfs(int n,int k,int sec){
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{n,sec});
        visited[n]=true;
        while(!q.isEmpty()){
            int loc[]=q.poll();
            if(loc[0]==k){second=loc[1];break;}
            int move[]={loc[0]-1,loc[0]+1,loc[0]*2};
            
            for(int i=0;i<3;i++){
                if(move[i]>=0&&move[i]<=100000&&!visited[move[i]]){
                    visited[move[i]]=true;
                    q.offer(new int[]{move[i],loc[1]+1});
                }
            }
            
        }
    }
}

보통의 BFS에서는 큐가 비어질때까지 반복을 멈추지 않는데 해당 문제에서는 수빈이가 동생의 위치에 도달하면 반복을 종료해야 하기 때문에 loc [0]==k라는 조건을 통해 수빈이가 도달 시 현재 초값을 sceond에 저장하고 반복을 종료하도록 코드를 작성하였다.

 

  마무리  

해당 문제에서 중요한 부분을 초를 따로 관리하지 않고 bfs의 매개변수로 넘기어 수빈이가 동생에게 도달했을 때 값을 경신해 초값 관리를 수월하게 하는 부분이라 생각되고 이 부분을 유념해 문제를 풀이하면 좋을 것 같다.

또 해당 문제에서는 DFS로는 풀이가 불가능하다. 그이유는 최소 시간이려면 최소로 이동해야하기 때문에 DFS를 사용할 경우 그렇지 못한 경우가 발생해 부적합하다는 부분도 알고 가면 좋겠다.