[백준] 알고리즘 분류(그래프 이론,JAVA)12851번, 숨바꼭질 2

문제 링크

12851번: 숨바꼭질 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 수빈이는 1초동안 X+1, X-1, X × 2으로 이동할 수 있습니다.

2. 수빈이가 동생의 위치에 도달할 때 최소 시간과 최소 시간이 걸리는 방법의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 수빈이가 이동하는 경우를 탐색합니다.

 

3. 탐색이 끝난 뒤 최소 시간과 방법의 개수를 결과로 출력합니다.

 

수빈이 탐색!

 

※동생이 수빈이보다 더 작은 위치에 존재할 때에는 후진밖에 할 수 없으므로 항상 최소 시간은 N-K이고 방법은 1개입니다.

 

아래 행동은 동생이 수빈이보다 더 큰 위치에 존재할 때 탐색합니다.

 

수빈이는 동생을 찾는 것에 있어서 3가지 행동

 

전진(X+1)

X가 동생의 위치보다 크면 전진해도 동생에게 도착하지 못합니다.

(X < 동생의 위치) 가 성립할 때 전진!

 

 

후진(X-1)X가 0보다 작아지면 동생에게 도착할 수 없습니다.

(X ≥ 0)가 성립할 때 후진!

 

순간이동(X × 2)X를 2배했을 떄 동생의 위치보다 너무 커지면 최단 시간으로 할 수 없습니다.

(X ≤ (동생의 위치 + 2)/2)가 성립할 때 순간이동!

 

행동하면서 다른 위치에 방문할 때 해당 시간보다 먼저 방문한 적이 있으면 최소 시간이 될 수 없기 때문에 넘깁니다.

 

각 위치에 방문 시간은 visited[]라는 배열을 통해서 저장하도록 하였습니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 5

K : 17

 

2. 수빈이가 이동하는 경우를 탐색합니다.

 

※동생의 위치가 수빈이의 위치보다 크기 때문에 탐색 진행!

 

수빈이 행동 진행!

 

수빈이의 위치 :  5

 

전진 : 5 + 1 = 6(1초)

후진 : 5 - 1 = 4(1초)

순간이동 : 5 × 2 = 10(1초)

 

수빈이의 위치 :  6

 

전진 : 6 + 1 = 7(2초)

후진 : 6 - 1 = 5(2초) X

: 5는 초기 위치로 방문 최소 시간 0이므로 2초보다 작으므로 후진 진행 X

순간이동 : 6 × 2 = 12(2초)

 

수빈이의 위치 :  4

 

전진 : 4 + 1 = 5(2초) X

: 5는 초기 위치로 방문 최소 시간 0이므로 2초보다 작으므로 후진 진행 X

후진 : 4 - 1 = 3(2초)

순간이동 : 4 × 2 = 8(2초)

 

탐색 진행......

 

 

최소 시간으로 동생에게 도착했을 때

 

5 ▶ 10 ▶ 9 ▶ 18 ▶ 17

5 ▶ 4 ▶ 8 ▶ 16 ▶ 17

 

3. 탐색이 끝난 뒤 최소 시간과 방법의 개수를 결과로 출력합니다.

 

5 ▶ 10 ▶ 9 ▶ 18 ▶ 17

5 ▶ 4 ▶ 8 ▶ 16 ▶ 17

 

최소 비용 : 4초

방법 : 2개

 

4

2

결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N, K를 띄어쓰기 기준 나누었습니다.
• 동생의 위치가 수빈이보다 클 경우 search함수를 이용하여 최소 시간 및 방법 개수를 탐색합니다
• 동생의 위치가 수빈이보다 작거나 같으면 최소 시간은 N-K, 방법은 1개입니다.
• 최소 시간과 방법의 개수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 BFS를 이용해서 수빈이가 움직일 수 있는 경우를 탐색합니다.
• search함수는 동생에게 도착했을 때 최소 시간과 방법의 개수를 계산합니다.

 

결과코드

 

import java.io.*;
import java.util.*;

public class Main {
    //수빈이 위치 관련 정보
    static class info{
        int position, value;	//position : 현재 위치, value : 초
        public info(int position, int value){
            this.position = position;
            this.value = value;
        }
    }
    static int count = 0;	//최소 시간 방법 저장 변수
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        //동생의 위치가 수빈이보다 클 경우
        if(N < K) {
            int[] visited = new int[K + 3];
            Arrays.fill(visited, Integer.MAX_VALUE);	//각 위치 시간 최대값으로 초기화
            search(N, K, visited);		//탐색 진행!
            bw.write(visited[K] + "\n" + count);	//최단 시간 및 방법 BufferedWriter 저장
        }else	//동생의 위치가 수빈이보다 작거나 같은 경우
            bw.write((N-K) + "\n1");

        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //수빈이 행동 BFS을 통한 탐색 진행하는 함수
    static void search(int N, int K, int[] visited){
        Queue<info> q = new LinkedList<>();
        q.add(new info(N, 0));	//수빈이 초기 위치 Queue 저장
        visited[N] = 0;	//초기 위치 시간 0으로 설정
        //BFS 탐색 진행
        while(!q.isEmpty()){
            info cur = q.poll();
            //동생에게 도착했을 때
            if(cur.position == K){
                if(cur.value == visited[K])	//현재 최소 시간과 동일할 때
                    count++;
                else if(cur.value < visited[K])	//현재 최소 시간보다 더 빨리 도착했을 때
                    count = 1;
                continue;
            }
            int next;
            //수빈이 3가지 행동 조건에 만족할 때 수행!
            //전진!
            if(cur.position < K){
                next = cur.position + 1;
                if(cur.value + 1 <= visited[next]){
                    visited[next] = cur.value + 1;
                    q.add(new info(next, cur.value + 1));
                }

            }
            //후진!
            if(cur.position != 0){
                next = cur.position - 1;
                if(cur.value + 1 <= visited[next]){
                    visited[next] = cur.value + 1;
                    q.add(new info(next, cur.value + 1));
                }
            }
            //순간이동!
            if(cur.position <= (K + 2)/2){
                next = cur.position * 2;
                if(cur.value + 1 <= visited[next]){
                    visited[next] = cur.value + 1;
                    q.add(new info(next, cur.value + 1));
                }
            }
        }
    }
}