[BOJ - JAVA] 1697 - 숨바꼭질(BFS)

# 주소

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

1697번: 숨바꼭질

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    public static int[] dx = {1,-1};
    public static int n,m;
    public static int count;
	public static int arr[] = new int[100001];
	public static void main(String[] args){
	    Scanner scan = new Scanner(System.in);
	    n = scan.nextInt();
	    m = scan.nextInt();
	    count = 0;
	    if(n == m) {
	    	System.out.println(0);
		}else {
    		bfs(n);
    	}
	}
    public static void bfs(int n) {
    	Queue<Integer> queue = new LinkedList<>();
    	queue.add(n);
    	arr[n] = 1;
    	while(!queue.isEmpty()) {
    		int now = queue.poll();
    		for(int i = 0; i < 3; i++) {
    			int next;
    			if(i == 0)
    				next = now + 1;
    			else if(i == 1)
    				next = now - 1;
    			else
    				next = now * 2;
    			if(next == m) {
    				System.out.println(arr[now]);
    				return;
    			}
    			if(next >= 0 && next < arr.length && arr[next] == 0) {
    				queue.add(next);
    				arr[next] = arr[now] + 1;
    			}
    		}
    	}
    }
}

 

BFS, DFS에 이렇게 집착하는 것도 앞으로 있을 코딩테스트의 최다빈출 문제가 이 파트이기 때문입니다.

오죽하면 BFS, DFS만 공부해도 과거엔 합격한다는 말도 있었으니까요.

이번에 소개할 문제는 숨바꼭질입니다. 정답률이 24%밖에 안되서 왜지... 했는데 생각보다 코드는 간결한데 섬뜩 생각하기 어려운 부분이 많더라고요. 

 

제일먼저 main{ 안의 코드를 보시면 n과 m을 입력받고 n == m일 때 0을 출력, 아닐 때 bfs(n)을 실행한다고 작성했습니다. 당연한 거겠죠?? 하지만 문제의 부분은 bfs내부에서 일어납니다.

bfs에 정수 인자 int n을 입력받고 Queue를 선언합니다.

그리고 queue에 add 또는 offer하여 n을 집어 넣습니다.

그리고 while문 내부로 들어가서 (!queue.isEmpty())는 모든 queue문의 핵심)

now = queue.poll()로 갖고와서 now에 담겠습니다.

이후 for문을 통해 각 i의 값에 다라 next라는 값에 now + 1을 하거나 now - 1을 하거나 now * 2를 합니다.

그러다 만약 next 와 m이 같아지면 arr[now]를 출력하고 return합니다.

이 arr[now]는 그 밑에서 작성이 됩니다.

만약 next가 0보다 크거나 같고 arr크기보다 크지 않으며 arr[next]값이 0이면(조회하지 않은 인덱스) queue에 next를 추가하고 arr[next] = arr[now] + 1을 하여 arr를 써내려갑니다.

여기서 의문이 들 수 있습니다. 분명 문제에서는 최단시간 안에 now가 next에 도달하도록 짜는 것인데 단순히 for문 가지고 값을 넣어가며 정답을 맞출 수 있는지에 대해서 말이죠.

 

생각해보겠습니다. 예제문에 나와있는 그대로 맞춰가보겠습니다. 입력 예제는 5 17이었습니다.

그럼 queue에 5가 담길테고 now또한 5가 됩니다. 그리고 나서 for문에서 i = 0이기 때문에 next 값은 5 + 1이되어 6이됩니다. 이 6은 밑으로 쭉 내려가서 m값과 다르므로 다시 내려가서 제일 밑의 if문에 도달합니다.

이 때 모든 if조건을 만족하므로 queue에는 6이 담깁니다. 다만 arr[6] = 2가 됩니다.

여기서 다시 for문으로 들어가, i = 1일 때가 실행됩니다. 이 때는 now 값이 여전히 5이기 때문에 next 는 4가 되는 것입니다. 그러므로 arr[4] = arr[5] + 1이므로 2가 됩니다.

마지막으로 i = 2일 때, now * 2 = 10이므로 next는 10이됩니다. 그리고 arr[10] = 2가 됩니다.

즉, 1초가 지났을 때를 표로 살펴보면

4	5	6	7	8	9	10	11	12	13
1	0	1				1

이런식으로 입력되는 것입니다. 더 나아가서 보겠습니다.

2초가 지났을 때는 어떻게 나타낼 수 있을까요?

3	4	5	6	7	8	9	10	11	12
2	1	0	1	2		2	1	2

감이 오시나요?

그럼 3초가 지났을 떄는 어떻게 표현될까요?

3	4	5	6	7	8	9	10	11	12
2	1	0	1	2	3	2	1	2	2

그리고 인덱스가 20인 것 까지 같이 보여드리겠습니다.

11	12	13	14	15	16	17	18	19	20
2	2	3	2	3			3	3	2

이렇게 짜여집니다.

마지막으로 4초가 지났을 때는 16과 17의 값이 각각 4가 되면서 17로 이동하기 위해 우리는 4초가 필요하단 것을 알 수 있게 되었습니다!!

감사합니다.