[JAVA] 백준 13913 : 숨바꼭질 4

문제

13913번: 숨바꼭질 4

 

해결 방법

오랜만에 알고리즘 해설을 준비했는데, 그리 어렵지 않은 문제이다.

어려운 문제는 어떻게 풀어야 할지 아직 감이 잘 안 잡혀서, 문제를 풀더라도 설명을 할 정도로 이해를 하지 못해 가져오지 못했다.

 

이 문제는 수빈이가 동생을 찾는 숨바꼭질 문제인데,

수빈이는 현재 위치에서 +1, -1 또는 x2 만큼 움직일 수 있고 움직일 때마다 1초씩 소모된다.

즉, 모든 경우의 수를 전부 확인하며 목표지점에 도달하는 시간을 체크하면 된다.

 

BFS를 사용하게 되면 가장 빠른 경우의 수가 제일 먼저 도착하게 되기 때문에 간단하게 코드를 짤 수 있다.

나는 현재 위치와 총 소모한 시간을 class로 구성해서 같이 포함시켜 Queue에 넣어 돌렸다.

 

또 이동한 지점을 출력해주어야 하는데, class에 ArrayList를 추가해서 방문한 모든 곳을 기록해두는 방법도 있지만 효율적이지 못하고, 방문 확인을 통해 각 지점을 한 번씩만 지나가기 때문에 각 지점을 방문하기 직전에 어디를 방문했는지만 기록해서 역추적을 사용하는 편이 나을 거라 생각해 parent 배열을 통해 이 지점에 방문하기 직전 방문한 곳을 기록하였다.

 

그래서 동생 위치에 도달했을 때 시간을 먼저 출력하고,

parent 배열을 역으로 타고 가며 수빈이의 위치에 도착할 때까지 Stack에 값을 저장해주었다.

Stack을 사용하는 것은 후입 선출의 Stack 특성상 먼저 넣은 정보가 가장 나중에 나오기 때문에 역으로 넣은 정보를 올바른 방향으로 출력하기가 편하기 때문이다.

물론 ArrayList에 값을 넣고 역으로 출력을 해도 문제는 없다.

 

코드

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

public class Bj_13913 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		boolean visit[] = new boolean[100001];
		int parent[] = new int[100001];
		
		Queue<Position> q = new LinkedList<>();
		q.offer(new Position(N, 0));
		visit[N] = true;
		
		while (!q.isEmpty()) {
			Position temp = q.poll();
			
			if (temp.current == K) {
				System.out.println(temp.time);
				
				// 역추적은 후입선출인 Stack을 활용하면 편하다.
				Stack<Integer> stack = new Stack<>();
				int a = temp.current;
				while (a != N) {
					stack.add(a);
					a = parent[a];
				}
				// 위의 반복문엔 시작점인 N이 포함되지 않았기때문에 추가시켜준다.
				stack.add(a);
				
				while (!stack.isEmpty()) {
					System.out.print(stack.pop() + " ");
				}
				
				break;
			}
			
			if (temp.current + 1 < 100001 && !visit[temp.current + 1]) {
				q.offer(new Position(temp.current + 1, temp.time + 1));
				visit[temp.current + 1] = true;
				parent[temp.current + 1] = temp.current;
			}
			
			if (temp.current - 1 >= 0  && !visit[temp.current - 1]) {
				q.offer(new Position(temp.current - 1, temp.time + 1));
				visit[temp.current - 1] = true;
				parent[temp.current - 1] = temp.current;
			}
			
			if (temp.current * 2 < 100001 && !visit[temp.current * 2]) {
				q.offer(new Position(temp.current * 2, temp.time + 1));
				visit[temp.current * 2] = true;
				parent[temp.current * 2] = temp.current;
			}

		}
	}

}

class Position {
	int current;
	int time;
	
	Position (int current, int time) {
		this.current = current;
		this.time = time;
	}
}