[BJ] 13913 : 숨바꼭질

       문제 요약        

- 문제

 

 

- 입출력

 

         아이디어        

 

단순하게 풀면 시간초과가 난다

부모 배열을 둬서 경로를 저장하는 아이디어가 필요하다

 

parent[다음위치] = 현재위치;

 

아래 코드 처럼 맨 마지막 위치에서부터 거슬러 맨 처음위치까지 parent 배열을 탐색하면

경로를 거꾸로 탐색하는 것과 같은 의미가 된다

그래서 Stack 자료구조를 사용해서 경로를 뒤집었다

int start = K;

Stack<Integer> stack = new Stack<>();

stack.add(start);

 

while(start != N) { // 거꾸로 올라가야 함

stack.add(parent[start]);

start = parent[start];

}

         소스코드        

- 정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

class Main {
	static int N, K; // 수빈이가 있는 위치, 동생이 있는 위치
	static int[] parent;
	static int[] time;
	public static void main(String[] args)throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 수빈이가 있는 위치
		K = Integer.parseInt(st.nextToken()); // 동생이 있는 위치
		
		parent = new int[100001];
		time = new int[100001];
		
		bfs();
		
		int start = K;
		Stack<Integer> stack = new Stack<>();
		stack.add(start);
		
		while(start != N) { // 거꾸로 올라가야 함
			stack.add(parent[start]);					
			start = parent[start];
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append((time[K] - 1)+"\n");
		while(!stack.isEmpty()) {
			sb.append(stack.pop()+" ");
		}
		
		System.out.println(sb.toString());
		
	}
	static void bfs() {
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(N);
		time[N] = 1;
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			if(now == K) {
				return;
			}
			if(isValid(now * 2)) {
				queue.add(now * 2);		
				parent[now * 2] = now;
				time [now * 2] = time[now] + 1;
			}
			if(isValid(now - 1)) {
				queue.add(now - 1);				
				parent[now - 1] = now;
				time [now - 1] = time[now] + 1;

			}
			if(isValid(now + 1)) {
				queue.add(now + 1);
				parent[now + 1] = now;
				time [now + 1] = time[now] + 1;

			}
			
		}
	}
	static boolean isValid(int x) {
		return x >= 0 && x <=100000 && time[x] == 0;
	}
}

- 시간 초과 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
	static int N, K; // 수빈이가 있는 위치, 동생이 있는 위치
	static boolean[] visited;
	public static void main(String[] args)throws Exception{
		StringBuilder sb = new StringBuilder();
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 수빈이가 있는 위치
		K = Integer.parseInt(st.nextToken()); // 동생이 있는 위치
		
		visited = new boolean[100001];
		Queue<Node> queue = new ArrayDeque<>();
		queue.add(new Node(N,""+N,0));
		
		while(!queue.isEmpty()) {
			Node now = queue.poll();
			if(now.position == K) {
				System.out.println(now.moveCnt);
				System.out.println(now.command);
				return;
			}
			
			if(visited[now.position])continue;
			visited[now.position] = true;
			
			if(isValid(now.position * 2))
				queue.add(new Node (now.position * 2, now.command+" "+(now.position * 2), now.moveCnt + 1));
			if(isValid(now.position - 1))
				queue.add(new Node (now.position - 1, now.command+" "+(now.position - 1), now.moveCnt + 1));
			if(isValid(now.position + 1))
				queue.add(new Node (now.position + 1, now.command+" "+(now.position + 1), now.moveCnt + 1));
			
		}
	}
	static boolean isValid(int x) {
		return x >= 0 && x <=100000 && !visited[x];
	}
	static class Node {
		int position;
		String command;
		int moveCnt;

		Node(int position, String command, int moveCnt){
			this.position = position;
			this.command = command;
			this.moveCnt = moveCnt;
		}
	}
	
}