[백준] 12851 숨바꼭질 2 - BFS JAVA

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

12851번: 숨바꼭질 2

코드설명

BFS를 활용하는 문제입니다.

 

이 문제에서 BFS의 핵심은, time 배열입니다. 일반적으로 BSF를 진행하면 visited 배열로 단순하게 방문했는지, 방문하지 않았는지 여부를 체크하며 BFS를 진행합니다.

 

우선, 첫번째 생각해본 방식은,.

visited[][3] 의 형식으로 +1 로 들어왔을때, -1, *2 로 들어왔을때의 3가지 방문배열을 설정하여 진행하려 했습니다. 하지만, 이 방식으로 진행할경우 처음에는 다른방식으로 가더라도 이후에 같은방식으로 겹칠경우 해당 경우를 셀수가 없습니다. ( 즉, 모든 경우를 탐색하지 못함 ) 이 경우는 불가능합니다. 

 

해결방안은, 

BFS는 Queue를 활용하므로, 가장 먼저 들어간것이 가장 먼저 나오는 구조입니다.

이 구조에서는 결국, 이동횟수가 작은것들 ( 1번째 연산한것, 1번째 연산한것, 1번째 연산한것, 2번쨰 연산 한것.. ) 이런식으로 연산의 순서에 따라 Queue가 나오게됩니다.

그렇기에, 해당 구조를 이용하여 같은 위치에 같은 시간에 도착한다면(  이전의 것보다 더 빠르게 도착할 가능성은 없음. 큐는 선입선출 구조이기 때문, 더 느리게 도착한다면 해당 방안은 이미 다른 연산을 통해서 왔거나 이미 최적의 방안이 아닙니다.) 서로 다른 방안을 통해서 같은 공간에 도착한것으로 판단할 수 있습니다.

 

그러므로 time[다음위치] == 현재위치에서의 연산 + 1 과 같다면, 같은 연산횟수를 사용한것과 같습니다. 일종의 방문처리를 통해서 여러 방안을 count할 수 있습니다.

코드

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 Main {
	public static int N, K;
	public static int[][] map;
	public static int[] time= new int[100001]; //각 위치별 처음 도착한 시간
	public static int[] dp;
	public static int answer = 0;
	public static int minCnt = Integer.MAX_VALUE;
	public static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N= Integer.parseInt(st.nextToken());
    	K= Integer.parseInt(st.nextToken());
    	
    	
    	q.offer(new Node(N, 0));
    	time[N] = 1;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int pos = temp.pos;
    		int cnt = temp.cnt;
    		
    		if( minCnt < cnt ) continue;
    		if( pos < 0 || pos > 100000) continue;
    		
    		if(pos == K ) {
    			if(minCnt > cnt) { //만약 최소거리를 찾는다면 초기화
    				minCnt = cnt;
    				answer = 0;
    			}
    			
    			if(minCnt == cnt) {
    				answer += 1;	
    			}
    			continue ;
    		}
    		
    		if(pos + 1 <= 100000) {
        		if(time[pos + 1] == 0 || time[pos + 1] == cnt + 1) {
        			time[pos + 1] = cnt + 1;
        			q.offer(new Node(pos + 1, cnt + 1));	
        		}    			
    		}
    		
    		if(pos -1 >= 0) {
        		if(time[pos - 1] == 0 || time[pos - 1] == cnt + 1) {
        			time[pos - 1] = cnt + 1;
        			q.offer(new Node(pos - 1, cnt + 1));	
        		}    			
    		}

    		if(pos * 2 <= 100000) {
        		if(time[pos * 2] == 0 || time[pos * 2] == cnt + 1) {
        			time[pos * 2] = cnt + 1;
        			q.offer(new Node(pos * 2, cnt + 1));	
        		}    			
    		}
    		
    	}
    	System.out.println(minCnt);
    	System.out.println(answer);
    }
    
    
    
}

class Node{
	int pos;
	int cnt;
	public Node(int pos, int cnt) {
		this.pos = pos;
		this.cnt = cnt;
	}
}