[백준][JAVA] 1697 : 숨바꼭질

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

1697번: 숨바꼭질

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] minTime = new int[100005];
        Arrays.fill(minTime, -1);

        System.out.println(BFS(N, K, minTime));
    }

    public static int BFS(int N, int K, int[] minTime) {
        int nowN = N;
        int[] status = new int[3];
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(nowN);
        minTime[nowN] = 0;

        while (!queue.isEmpty() && nowN != K) {
            nowN = queue.poll();
            
            status[0] = nowN - 1;   
            status[1] = nowN + 1;  
            status[2] = nowN * 2;    

            for (int i = 0; i < 3; i++) {
                if (status[i] >= 0 && status[i] <= 100000) {
                    if (minTime[status[i]] == -1) {
                        queue.add(status[i]);
                        minTime[status[i]] = minTime[nowN] + 1;
                    }
                }
            }
        }
        return minTime[K];
    }
}

 

1. main 부

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] minTime = new int[100005];
        Arrays.fill(minTime, -1);

        System.out.println(BFS(N, K, minTime));
    }

 

 N, K  : 수빈이가 있는 위치 N과 동생이 있는 위치 K를 저장할 변수

 minTime  : 해당 칸까지 가는 데 걸리는 최소 시간을 담은 배열

 

- Arrays.fills 함수를 사용하여  minTime  의 모든 칸을 -1로 초기화 한다.

- BFS 함수에  N, K  와  minTime  배열을 전달한다.

 

 

2. BFS 함수

    public static int BFS(int N, int K, int[] minTime) {
        int nowN = N;
        int[] status = new int[3];
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(nowN);
        minTime[nowN] = 0;

        while (!queue.isEmpty() && nowN != K) {
            nowN = queue.poll();
            
            status[0] = nowN - 1;   
            status[1] = nowN + 1;  
            status[2] = nowN * 2;    

            for (int i = 0; i < 3; i++) {
                if (status[i] >= 0 && status[i] <= 100000) {
                    if (minTime[status[i]] == -1) {
                        queue.add(status[i]);
                        minTime[status[i]] = minTime[nowN] + 1;
                    }
                }
            }
        }
        return minTime[K];
    }
}

 

 

 - (1)

    public static int BFS(int N, int K, int[] minTime) {
        int nowN = N;
        int[] status = new int[3];
        Queue<Integer> queue = new LinkedList<Integer>();
        
        queue.add(nowN);
        minTime[nowN] = 0;

 nowN  : nowN에서 다음으로 갈 세 군데의 칸을 탐색한다.

 status  : 다음에 이동할 index를 저장할 배열

 queue  : 다음으로 이동한 index를 add 할 queue

 

-  nowN  에는 최초에 수빈이가 있는 위치인 N을 저장한다.

- 수빈이는 한 번에 X-1, X+1, 2*X 중 하나로 이동이 가능하므로  status  는크기가 3인 배열로 선언한다.

- 최초 수빈이가 서있는 자리의 index를  queue  에 add 한다.

- 최초 수빈이가 서있을 때를 0초로 하기 때문에 해당 칸을 0으로 초기화한다.

 

 

- (2)

        while (!queue.isEmpty() && nowN != K) {
            nowN = queue.poll();
            
            status[0] = nowN - 1;   
            status[1] = nowN + 1;  
            status[2] = nowN * 2;

- while 종료 조건 : queue가 비었거나 nowN이 K일 경우(동생 칸까지 온 경우)

-   queue  에 있는 요소 중 가장 먼저 들어간 것을 꺼내  nowN  을 초기화 시킨다. (최초 poll의 경우 이전과 동일하게 수빈이가 최초 서있는 자리)

- 현재 서있는 곳의 뒤로 한칸, 앞으로 한칸, 순간 이동한 위치를  status  에 차례로 저장한다.

 

 

- (3)

            for (int i = 0; i < 3; i++) {
                if (status[i] >= 0 && status[i] <= 100000) {
                    if (minTime[status[i]] == -1) {
                        queue.add(status[i]);
                        minTime[status[i]] = minTime[nowN] + 1;
                    }
                }
            }
        }
        return minTime[K];
    }
}

 

 for (int i = 0; i < 3; i++) {

-  status  배열을 차례로 순회한다.

 

if (status[i] >= 0 && status[i] <= 100000) {

-  status  배열에 저장한 값의 범위가 배열을 벗어나지 않았는지 확인

ex) 5에서 시작하여 계속 X-1 칸으로 가면 6초 뒤에는 -1 칸을 검사하게 된다.

 

                    if (minTime[status[i]] == -1) {
                        queue.add(status[i]);
                        minTime[status[i]] = minTime[nowN] + 1;
                    }
                }
            }
        }
        return minTime[K];
    }
}

- 이전에 방문했는지(status[i]칸에 대한 minTime이 -1이 아닌지) 확인 한다.

    → 이전에 방문했다면 현재 방문한 것보다 이전에 방문한 것이 더 빠른 시점이므로 초기화하지 않는다.

- 처음 탐색하는 index라면  queue  에 넣고, 해당 minTime을 전 위치값 +1 을 해준다.

- while 문이 종료되면 minTime[K]를 반환한다.

 

 

< 자세한 queue 변화 모습 >

 

while문을 돌기 전  minTime  배열,  queue  모습  /  nextN = 5

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
-1	-1	-1	-1	-1	0	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1

5

 

while문을 1바퀴 돌고 난 후  minTime  배열 모습 /  nextN = 5

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
-1	-1	-1	-1	1	0	1	-1	-1	-1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1

4

6

10

 

while문을 2바퀴 돌고 난 후  minTime  배열 모습 /  nextN = 4

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
-1	-1	-1	2	1	0	1	-1	2	-1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1

6

10

3

8

 

while문을 3바퀴 돌고 난 후  minTime  배열 모습 /  nextN = 6

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
-1	-1	-1	2	1	0	1	2	2	-1	1	-1	2	-1	-1	-1	-1	-1	-1	-1

10

3

8

7

12

 

while문을 4바퀴 돌고 난 후  minTime  배열 모습 /  nextN = 10

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
-1	-1	-1	2	1	0	1	2	2	2	1	2	2	-1	-1	-1	-1	-1	-1	-1

3

8

7

12

9

11

20

(자리 부족으로 19까지만 minTime 배열 표현)

 

while문을 5바퀴 돌고 난 후  minTime  배열 모습 /  nextN = 3

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
-1	-1	3	2	1	0	1	2	2	2	1	2	2	-1	-1	-1	-1	-1	-1	-1

8

7

12

9

11

20

2

 

while문을 6바퀴 돌고 난 후  minTime  배열 모습 /  nextN = 8

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
-1	-1	3	2	1	0	1	2	2	2	1	2	2	-1	-1	-1	3	-1	-1	-1

7

12

9

11

20

2

16

 

...

 

while문을 16바퀴 돌고 난 후  minTime  배열 모습 /  nextN = 16

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
-1	4	3	2	1	0	1	2	2	2	1	2	2	2	2	4	3	4	2	2

14

13

24

18

22

19

21

40

1

15

17

32

→ 여기서 17의 minTime이 최초로 결정된다. 이후 nextN이 17이 되어 해당 index에 대한 X-1, X+1, 2*X를 탐색 후 while문이 종료되어 minTime[17]이 함수의 return 값으로 반환된다.