백준 1697번: 숨바꼭질

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

1697번: 숨바꼭질

Source Code: https://github.com/JangAJang/Study/blob/main/백준_그래프와%20순회/숨바꼭질/src/Main.java

이전에 풀었던 BFS와 똑같이 큐로 접근해야겠다는 생각이 들었다( 이전 bfs문제에서 배열을 쓰다가 시간 낭비가 상당했다)

 

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

bfs에서는 boolean형으로 방문했는지 안했는지를 판단해주는게 중요하다. 이 부분에서 바로

 

boolean[] visited = new boolean[100001];

이게 생각이 났다. 

visited 처리를 해서 무한 반복을 방지할 수 있다.(경우에 따라 위치를 +1 하고 다음에 -1하고 다시 +1하고 다시 -1하고....)

 

또한 주소와 움직인 횟수를 저장하는 객체를 만들었다. 

public static class Place{
    int location;
    int count;

    public Place(int location, int count){
        this.location = location;
        this.count = count;
    }
}

나는 항상 객체로 만드는게, new int[]{location, count}로 할 수 있겠지만, 나중에 다시 볼때 이게 뭐였는지, 왜 이런지 다른 사람들도 이해했으면 좋겠기 때문이다. 

 

이제 큐에 대한 구현을 생각해보았다. 

1. 큐에 시작 점을 넣는다. 
2. 반복문으로 들어간다. 
3. 큐에서 제일 마지막을 뽑아낸다.
4. 다음 이동 위치를 계산한다. (+1, -1, *2)
5. 계산한 이동 위치들을 큐에 넣는다(이 때 움직인 횟수를 1 늘려준다. ) visited = true로 바꾸어 준다. 

여기에 중요한 것은, 이동위치가 100000을 넘을 때, 이동위치가 이미 갔던 곳일 때 큐에 넣지 않는다는 것이다. 

 

이를 코드화 시키면 아래같이 나온다. 

Queue<Place> queue = new LinkedList<>();
queue.add(new Place(subin, 0));
visited[subin] = true;
while(!queue.isEmpty()){
    Place now = queue.poll();
    if(now.location == brother) result = Math.min(result, now.count);
    else{
        int[] arr = new int[3];
        arr[0] = now.location + 1;
        arr[1] = now.location - 1;
        arr[2] = now.location * 2;
        for(int i=0; i<3; i++){
            if(arr[i] < 0 || arr[i] > 100000) continue;
            else if(visited[arr[i]]) continue;
            queue.add(new Place(arr[i], now.count+1));
            visited[arr[i]] = true;
        }
    }
}

결과는 최대 움직이는게 0에서 100,000까지 10만번이기에 기본값으로 100,000으로 두고 Math.min을 썼다. 

 

입출력을 받아서 

풀었다!!!!