[백준/JAVA] 13913번 : 숨바꼭질4(BFS)

 

 

 

 

문제

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

13913번: 숨바꼭질 4

 

 

 

 

 

풀이

숨바꼭질(1697번) 문제와 유사하다. 다른 점이 있다면, 숨바꼭질4에서는 둘째 줄에 경로도 출력해야 한다는 점이다.

이 경우도 BFS로 풀 수 있다.

숨바꼭질 문제에 대한 BFS 풀이를 아래 글에서 확인해보고 오자.

2023.01.13 - [문제풀이/BFS] - [백준/JAVA] 1697번 : 숨바꼭질(BFS)

[백준/JAVA] 1697번 : 숨바꼭질(BFS)

 

 

 

 

이 문제도, ①n<k일 경우, ②n≥k일 경우의 두 가지 경우로 나누어 생각했다.

①n<k일 경우, BFS 알고리즘에 의해 결과를 출력한다.

② n≥k일 경우, 수빈이는 한 칸씩 뒤로 이동만을 반복하여 동생의 위치(k)에 도달할 수 있다.
     즉, 이 경우 최단시간으로 n-k를 출력하고, 경로는 n에서부터 k까지 값을 하나씩 줄여가며 출력한다.

//start는 n으로 수빈이의 위치를, k는 동생의 위치를 가르킨다
if(start >= k){
	System.out.println(start-k);
    for(int i = start; i>=k; i--)
    	System.out.print(i + " ");
    return;
}​

 

 

BFS 알고리즘

1. 이동 위치를 저장할 큐와 시간을 저장할 배열 visited, 이동할 위치의 이전 위치(현재 위치)를 저장할 배열 parent를 생성한다.

• 이 때, 배열은 각각 100001개로 초기화한다(위치가 0부터 100,000까지 가능하므로).

2. 수빈이의 현재 위치(처음 위치)를 큐에 저장하고, 현재 위치의 visited 값을 1로 한다

• visited의 값들은 모두 0으로 초기화되어 있다. 0인 경우는, 방문하지 않은 경우를 의미하므로 1부터 시작한다.

3. 큐가 빌 때까지 아래의 과정을 반복한다.

4. 큐에서 빼낸 x가 동생의 위치(k)와 같다면, 결과를 출력(printResult)하고 종료한다.

5. x-1, x+1, 2*x의 위치(next)에 대해 다음을 확인한다.

• next가 올바른 범위이고(0≤next≤100,000),visited[next]가 0일 경우(next의 위치를 방문하지 않았을 경우)
  • 큐에 next를 저장하고 visited[next]를 visited[x]+1의 값으로 저장한다.
  • parent[next]를 x로 저장한다(next 위치 이전의 위치가 x임을 저장하는 것).
  • 0일 경우에만 visited[next]를 갱신하는 이유는 최솟값을 찾기 위해서이다.

 

 

printResult 함수

• visited[k]는 동생의 위치까지 도달하기 위한 최단 시간 +1을 저장하므로 -1한 값을 출력한다.
• 경로를 출력하기 위해서 stack을 사용한다.
  • 수빈이는 처음 위치(수빈이의 위치)에서 동생의 위치까지 움직인다. 따라서 stack의 첫 원소는 k가 된다.
  • k에서부터 부모(parent배열)의 위치를 확인한다.
  • 부모가 n이 아닐때까지 반복하므로 n(수빈이의 처음 위치)는 stack에 push되지 않는다. 따라서 별도로 stack에 push하는 작업이 필요하다.
  • stack에 모든 노드를 push했다면 차례로 pop하면서 경로를 출력한다. 

 

 

 

코드

 

import java.util.*;

public class Main {
    private static int[] visited = new int[100001];
    private static int[] parent = new int[100001];

    private static void BFS(int start, int k){
        Queue<Integer> q = new LinkedList<Integer>();

        //start>=k일 때
        if(start >= k){
            System.out.println(start-k);
            for(int i = start; i>=k; i--)
                System.out.print(i + " ");
            return;
        }

        //start<k일 때, 시작 정점 큐에 넣고 시간=1
        q.offer(start);
        visited[start] = 1;

        while(!q.isEmpty()){
            int x = q.poll();
            
            //동생의 위치에 도달하면
            if(x==k) {
                printResult(start, k);
                return;
            }

            int next = 0;

			//x-1, x+1, x*2인 경우 모두 순회
            for(int i = 0; i<3; i++){
                if(i==0) next = x-1;
                if(i==1) next = x+1;
                if(i==2) next = x*2;

				//next위치를 방문하지 않은 경우
                if(next>=0 && next<=100000 && visited[next] == 0){
                    q.offer(next);
                    visited[next] = visited[x] + 1;
                    parent[next] = x;      //next의 이전 위치로 x를 저장
                }
            }
        }

    }

    private static void printResult(int n, int k){  //결과 출력 함수
        Stack<Integer> s = new Stack<>(); //스택 활용
        int idx = k; //마지막 위치(동생의 위치)

        //k부터 부모 노드를 저장
        while(idx!=n){
            s.push(idx);
            idx = parent[idx];
        }
        //시작 노드 추가
        s.push(idx);

        System.out.println(visited[k]-1);
        while(!s.isEmpty()){ //스택이 빌 때까지
            System.out.print(s.pop() + " ");
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        BFS(n, k);
    }
}