[BOJ] 백준 13549번 숨바꼭질3 (Java)

#13549 숨바꼭질3

난이도 : 골드 5

유형 : 그래프

13549번: 숨바꼭질 3

▸ 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

▸ 입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

▸ 출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

문제 풀이 

1차원 그래프에서 최단 거리를 구하는 문제이다. 이는 한 직선 상에서 수빈이가 이동할 수 있는 경로를 BFS로 탐색하면 되는데 해당 탐색 그래프의 가중치는 1과 0 두개만 있으므로 0-1BFS를 사용하면 된다.

 

📚 조건 정리

• 수빈 위치 (0 <= N <= 100,000)
• 동생 위치 (0 <= K <= 100,000)
•   그래프 이동 경로 총 3가지
  • 1) pos+1 , 가중치 1
  • 2) pos-1 , 가중치 1
  • 3) pos*2 , 가중치 0

 

일반 그래프 탐색이었다면 3가지의 경로를 특정 순서없이 탐색해도 됐지만 해당 문제는 그래프 간선마다 가중치가 있기 때문에 이 부분을 고려해서 탐색을 해야한다.

 

풀이 코드 

+1, -1은 가중치가 1이므로 queue 삽입순서를 가중치가 0인 순간이동 *2보다 뒤에 있어야한다.

import java.io.*;
import java.util.*;

public class Main {
	static int[] dx = {-1, 1};
	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());
		
        bfs(n, k);
	}
	
	static void bfs(int start, int destination) {
		Queue<int[]> q = new LinkedList<>();
		boolean[] check = new boolean[100_001];
		q.add(new int[]{start,0});
		check[start] = true;
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			int pos = p[0];
			int move = p[1];
			if(pos == destination) {
				System.out.println(move);
				return;
			}
			int jump = pos*2;
			if(jump < 100001 && !check[jump]) {
				check[jump] = true;
				q.add(new int[]{jump,move});
			}

			for(int i=0; i<2; i++) {
				int next = pos + dx[i];
				if (next>=0 && next <100001 && !check[next]) {
					check[next] = true;
					q.add(new int[]{next,move+1});
				}
			}
		}
	}
}

 

+

우선순위 큐 (Priorty Queue)를 사용하려면 queue안에서 순서가 바뀌기 때문에 방문여부체크를 queue를 뽑을 때 해줘야한다. 

import java.io.*;
import java.util.*;

public class Main {
	static class Node implements Comparable<Node>{
		int x;
		int move;
		public Node(int x, int move) {
			this.x =x;
			this.move =move;
		}
		@Override
		public int compareTo(Node o) {
			return this.move- o.move;
		}
	}

	// 생략 
    
	static void bfs(int start, int destination) {

		// 생략
        
		while(!q.isEmpty()) {
			Node p = q.poll();
			int pos = p.x; int move = p.move;
			check[pos] = true; // 여기서 방문여부체크!
			if(pos == destination) {
				System.out.println(move);
				return;
			}
			int jump = pos*2;
			if(jump < 100001 && !check[jump]) {
				q.add(new Node(jump,move));
			}

			for(int i=0; i<2; i++) {
				int next = pos + dx[i];
				if (next>=0 && next <100001 && !check[next]) {
					q.add(new Node(next,move+1));
				}
			}
		}
	}
}