41. 12851번 숨바꼭질2

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

12851번: 숨바꼭질 2

 

그래프 문제

 

이 문제는 이전 숨바꼭질 1문제와 다를것 없어보이지만 가장 중요한 차이점이 있다.

 

가장빠른시간으로 찾는 방법이 몇가지 인가? 라는 것 즉, 중복된 갯수를 세어야하는 작업이 추가된 셈

 

1. 입력 부분

public static void main(String[] args) throws IOException,NumberFormatException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		start = Integer.parseInt(st.nextToken());
		finish = Integer.parseInt(st.nextToken());

		//전으로는 순간이동 할 수 없다
		if(start>=finish){
			System.out.println(start-finish);
			System.out.println(1);
			return;
		}

		bfs();
		System.out.println(min);
		System.out.println(cnt);
	}

 

2. 탐색 부분

public static void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		
    	//큐에 수빈이의 위치를 넣어주고 탐색 표시
	queue.offer(start);
	visited[start] = 1;

	//큐가 빌때까지
	while(!queue.isEmpty()){
        //node는 수빈이의 위치
		int node = queue.poll();

		//최소수량보다 커졌을경우 리턴
		if(min < visited[node]) return;

		//배열에 담아주기
		int[] move = new int[]{node-1,node+1,node*2};
            
        	//right는 다음 이동한 위치
		for(int i=0; i<3; i++){
			int right = move[i];
			//수빈이의 다음 이동위치가 0,100000 위치를 벗어날경우
			if(right<0 || right>100000) continue;

			//잡았을 경우
			if(right == finish) {
				min = visited[node];
				cnt++;
			}
				
            		//못잡고 이동시 재이동
			if(visited[right]==0 || visited[right] == visited[node]+1){
				queue.offer(right);
				visited[right] = visited[node]+1;
			}
		}
	}
}

 

코드전문

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

public class training4 {
	private static int start;
	private static int finish;
	private static int min = Integer.MAX_VALUE;
	private static int cnt = 0; //초기값0
	private static int[] visited = new int[100001];
	
	
	public static void main(String[] args) throws IOException,NumberFormatException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		start = Integer.parseInt(st.nextToken());
		finish = Integer.parseInt(st.nextToken());

		if(start>=finish){
			System.out.println(start-finish);
			System.out.println(1);
			return;
		}

		bfs();
		System.out.println(min);
		System.out.println(cnt);
	}

	public static void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.offer(start);
		visited[start] = 1;

		while(!queue.isEmpty()){
			int node = queue.poll();

			if(min < visited[node]) return;

			int[] move = new int[]{node-1,node+1,node*2};
			for(int i=0; i<3; i++){
				int right = move[i];

				if(right<0 || right>100000) continue;

				if(right == finish) {
					min = visited[node];
					cnt++;
				}

				if(visited[right]==0 || visited[right] == visited[node]+1){
					queue.offer(right);
					visited[right] = visited[node]+1;
				}

			}
		}
	}
}

 

결과