백준 12851번: 숨바꼭질 2 [BFS][그래프] - Java

 

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

 

12851번: 숨바꼭질 2

가장 최단시간에 K에 도착한 경우의 수를 구하는 것.

package algorithm.boj;

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

public class Boj12851 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M =Integer.parseInt(st.nextToken());
		int K =Integer.parseInt(st.nextToken());
		
		Queue<Pos> q = new LinkedList<Pos>();
		
		q.add(new Pos(M,0));
		
		int ans = Integer.MAX_VALUE; //최단 시간
		int cnt = 0; // 방법의 가짓수
		int visit[] = new int[100001]; //각 위치별 cnt체크
		
		while(!q.isEmpty()) {
			Pos pos = q.poll();
			visit[pos.d]++; //큐에서 꺼낼때 방문처리할것, 3가지 경우의 수 돌때는 방문처리에 이상없도록
			
			
			if(pos.d == K) {
//				System.out.println(pos.d);
				//가장 짧은 시간에 도달..
				//첨도착하는게 제일 짧은시간일 것임.. 도착할때마다 ans와 시간이 같다면 ++해주어도 됨..
				ans = Math.min(ans, pos.time);
				if(ans==pos.time) {
					cnt++;
				}

				continue;
			}
			
			//3가지 방법 이동
			int dx[] = {pos.d+1, pos.d-1, pos.d*2};
			for (int i = 0; i < 3; i++) {
				
				//범위 벗어나는지?
				if(dx[i] > 100000 || dx[i] < 0)
					continue;
				
				if(visit[dx[i]]>0 && dx[i]!=K)
					continue;

				
				q.add(new Pos(dx[i],pos.time+1));
				
			}
		}
		
		System.out.println(ans);
		System.out.println(cnt);
	}
	
	static class Pos{
		int d;
		int time;
		
		public Pos(int d, int time) {
			this.d = d;
			this.time = time;
		}
	}

}