백준 숨바꼭질 4(13913)

숨바꼭질 4

1. 힌트

1) 위치한 점을 정점으로 하고 이동을 정점간의 간선으로 정의하면 이 문제는 최단 경로의 길이를 찾는 문제다. 만약 부분 문제들로 나눠서 DP로 풀려고 하면 문제들 간의 상호 의존성이 발생해서 불가능하다.

2) 간선의 가중치는 모두 1로 동일하므로 BFS를 사용하여 최단 경로의 길이를 구할 수 있다. 그런데 정점의 범위는 $1 \le x \le 10^5$일까?

3) BFS과정에서 인접한 정점을 검사할 때 마다, 해당 정점에 어느 정점에서 도달한 것인지 저장해놓는다. 정점은 한 번만 방문하므로 이전 정점은 유일하다. $K$까지의 최단 경로를 찾는 순간 이를 역추적 하면 실제 최단 경로중 하나를 구할 수 있다.

2. 접근

1) 뒤에서부터 생각해서 문제를 풀 수 있을까?

$N$에서 $K$까지의 최단 경로를 실제로 찾아내는 것은 어렵지만 정점마다 어느 정점에서 왔는지를 저장 해 놓으면 $K$에서 $N$으로 돌아가는 것은 쉽기 때문에 최단 경로를 실제로 찾아낼 수 있다.
정점의 범위는 어떻게 될까? 문제에서 $10^5$을 넘기면 안된다는 제약은 없지만 어떤 경우도 $10^5$를 넘기는 위치를 갔다가 오면 최적해가 될 수 없다. $10^5$를 넘어가는 경우는 $2*X$로 넘어가는 것인데 넘어가면 무조건 $X-1$로 돌아와야 한다. 그럴 바에는 $2 * X$를 하기 전에
$X-1$을 하는 것이 더 낫기 때문에 정점의 범위는 $1 \le x \le 10^5$이 된다.

3. 구현

public class Main {
	static int N; static int K;
	
	// here에서 way번째 방법으로 도착하는 곳 반환
	static int move(int here, int way) {
		switch (way) {
		case 0 : return here - 1;
		case 1 : return here + 1;
		case 2 : return 2 * here;
		}
		return -1;
	}
	
	static boolean inRange(int here) { return 0 <= here && here <= 100000; }
	
	static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.offer(N);
		int[] dist = new int[200000];
		Arrays.fill(dist, -1);
		dist[N] = 0;
		int[] parent = new int[200000];
		Arrays.fill(parent, -1);
		parent[N] = N;
		while (!q.isEmpty() || parent[K] == -1) {
			int here = q.poll();
			for (int d = 0; d < 3; d++) {
				int there = move(here, d);
				if (!inRange(there) || dist[there] != -1) continue;
				q.offer(there);
				dist[there] = dist[here] + 1;
				parent[there] = here;
			}
		}
		System.out.println(dist[K]);
		Stack<Integer> s = new Stack<>();
		for (int p = K; p != N; p = parent[p])
			s.push(p);
		s.push(N);
		StringBuilder ans = new StringBuilder();
		while (!s.isEmpty()) ans.append(s.pop()).append(" ");
		System.out.println(ans.toString().trim());
	}
	
	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());
		bfs();
	}
	
}

1) 시간 복잡도

2) 테스트 케이스