백준 1697 숨바꼭질 자바

숨바꼭질 문제 보러가기

1697번: 숨바꼭질

문제 설명

자바 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String [] input=br.readLine().split(" ");
        //5 17 4
        int n=Integer.parseInt(input[0]);
        int k=Integer.parseInt(input[1]);
        LinkedList<Integer> queue=new LinkedList<Integer>();
        int visitedTime[]=new int[100001];
        queue.add(n);
        while (!queue.isEmpty()){
            int chk=queue.peek();
            queue.poll();//제일 먼저 들어온 요소를 반환 한다.
            if(chk==k){
                System.out.print(visitedTime[chk]);
                System.exit(0);
            }
            if(chk-1>=0&&visitedTime[chk-1]==0){
                visitedTime[chk-1]=visitedTime[chk]+1;
                queue.add(chk-1);
            }
            if(chk+1<visitedTime.length&&visitedTime[chk+1]==0){
                visitedTime[chk+1]=visitedTime[chk]+1;
                queue.add(chk+1);
            }
            if(chk*2<visitedTime.length&&visitedTime[chk*2]==0){
                visitedTime[chk*2]=visitedTime[chk]+1;
                queue.add(chk*2);
            }
        }

    }

}

문제 풀이 

이번 문제는 BFS를 이용하여 풀면 됩니다. 얼마나 시간이 걸렸는지 체크하는 것이기 때문에 int[] visitedTime을 만들어서 

기존에 걸린 시간에서 +1 하는 방법으로 풀고 언니가 동생의 위치로 갔을때 해당 visitedTime 값을 출력하면 됩니다.

처음에는 방문확인을 위해 boolean값을 이용하였으나 int를 사용하여 시간을 같이 체크하였습니다. 해당 위치에 visitedTime이 0인 경우

방문 하지 않았기 때문에 방문확인도 같이 할 수 있었습니다.

• 시간 및 방문 확인을 위해 int[]배열을 만든다.
• BFS를 이용하여 언니의 위치값을 +1 , -1, *2 해준다.
• 언니의 위치값 변경 할때 방문을 했는지 체크하고 방문을 안했다면 이전 방문시간에+1을 하여 해당배열값에 넣어준다.
• 언니가 동생의 위치에 있을때 visitedTime 값을 출력한다.