[백준 12851] 숨바꼭질2 #bfs #visiting check 컨트롤

[설계]

1. State Space Tree 설계

 

① depth는 시간 (초)를 의미한다.

 

② 2번: 같은 depth에 있는 17은 "서로 다른 방법"을 통해 도달한 경우이다. 따라서, 일반적인 bfs처럼 큐 삽입시에 visiting check하면 안된다. (서로 다른 방법에 대한 고려가 안됨)

 

③ 1번: 문제의 목표는 "가장 빠른 시간"에 갈 수 있는 경우의 수이다. 즉, 이전 depth(더 빠른 시간)에 방문한 노드는 또 방문할 필요가 없다.

 

=> depth 단위로 끊어서 탐색하고, 1-depth가 끝나면 visiting check를 진행.

 

④ 종료조건: 방문노드 == 동생위치①

 

 

2. 시간복잡도 분석

위의 SST를 보면, 중복 방문의 경우가 존재하지만 visiting check를 통해 이전 depth에서 방문한 노드는 방문하지 않으므로 bfs탐색이 가능할 것으로 판단.

 

 

3. pruning 정리

1) visitied

2) 배열의 범위

 

 

 

---

[코드]

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

public class Main {
	static int N, K;
	static List<Integer> visitedList = new ArrayList<>();
	static boolean[] visited = new boolean[200010];
	static Queue<Integer> queue = 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());
		
		//starting point
		queue.add(N);
		int size = 0;
		int cur = 0, nxt = 0;
		int time = 0, cnt = 0, result = 0;
		boolean flag = false;
		while(!flag) { //큐를 사이즈만큼 나눠서 반복하기 위함
			
            //depth 단위로 끊어서 visiting check
			for(int i=0; i<visitedList.size(); i++) {
				visited[visitedList.get(i)] = true;
			}
			visitedList = new ArrayList<>();

			size = queue.size();
            
			while(size --> 0) {

				cur = queue.poll();

				if(cur == K) {
					result = time;
					cnt++;
					flag = true;
				} 
				
				if(flag == false) {

					for(int i=1; i<4; i++) {
						if(i==1) nxt = cur+1;
						else if(i==2) nxt = cur-1;
						else nxt = cur*2;

						if(0 <= nxt && nxt<100002 && !visited[nxt]) {

							visitedList.add(nxt);

							queue.add(nxt);
						}
					}
				}
			}
			time++;
		}
		System.out.println(result);
		System.out.println(cnt);
		
	}
}