[백준 1697] 숨바꼭질 - JAVA

https://www.acmicpc.net/problem/1697

문제 설명

---

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

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

입력

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

출력

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

문제 접근

---

• BFS 알고리즘을 사용한다(다른 방식으로도 가능).
• 현재 위치에서 수빈이가 갈 수 있는 곳을 모두 큐에 집어넣는다.
• 큐에서 꺼내면서 실제로 이동한다.
• 이동한 위치에는 그 위치에 도달하기까지 걸린 시간을 저장한다.
• 이미 저장된 시간이 있는 경우, 즉 이미 방문했던 곳은 가지 않는다(이미 가장 빠른 시간이 아니므로).

문제 풀이

---

	private static int N;
	private static int K;
	private static int[] location = new int[100001];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] temp = br.readLine().trim().split(" ");
		N = Integer.parseInt(temp[0]);
		K = Integer.parseInt(temp[1]);
		
		/* output */
		bw.write(""+bfs(N));
		bw.flush();
		bw.close();
	}

필요한 변수들을 선언하고 input을 받아온다. 실제 동작은 BFS 함수에서 이루어지므로 메인은 간단하다.

	public static int bfs(int n) {
		Queue<Integer> q = new LinkedList<Integer>();
		
		q.offer(n);
		location[n] = 0;
		
		while(!q.isEmpty()) {
			int x = q.poll();
			
			if(x == K) {
				return location[x];
			}
			if(0 <= x-1 && location[x-1] == 0) { //x-1
				q.offer(x-1);
				location[x-1] = location[x]+1; // +1sec
			}
			if(x+1 <= 100000 && location[x+1] == 0) { // x+1
				q.offer(x+1);
				location[x+1] = location[x]+1;
			}
			if(2*x <= 100000 && location[2*x] == 0) { // 2*x
				q.offer(2*x);
				location[2*x] = location[x]+1;
			}
		}
		return -1; // fail
	}

시작 위치의 도달 시간은 0이므로, location[n]에는 0을 넣고 시작한다. x는 현재 위치이며 큐에서 꺼낸 위치로 이동한다.

현재 위치가 목표 위치와 같아지면 그때의 시간을 반환한다.

그 아래의 if문들에서는 갈 수 있는 위치인지 판단하는데, 일단 좌표가 허용범위여야 하며 방문한 적이 없어야 한다. 셋 중 하나로 가는 것이 아니라 세 곳 다 가능성을 두고 탐색해야 한다. 갈 수 있는 곳의 좌표를 큐에 넣은 후, 그곳의 도달 시간을 저장한다. 현재 위치에서 1초면 갈 수 있기 때문에 현재 위치의 도달 시간 + 1을 해준다.

혹시나 아무 곳에도 갈 수 없으면(큐가 비는 경우) 불가능의 의미로 -1을 리턴해주었는데, 불가능한 테스트케이스는 나오지 않으므로 별 의미는 없다.

전체 코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class BFS1697 {

	private static int N;
	private static int K;
	private static int[] location = new int[100001];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] temp = br.readLine().trim().split(" ");
		N = Integer.parseInt(temp[0]);
		K = Integer.parseInt(temp[1]);
		
		/* output */
		bw.write(""+bfs(N));
		bw.flush();
		bw.close();
	}
	
	public static int bfs(int n) {
		Queue<Integer> q = new LinkedList<Integer>();
		
		q.offer(n);
		location[n] = 0;
		
		while(!q.isEmpty()) {
			int x = q.poll();
			
			if(x == K) {
				return location[x];
			}
			if(0 <= x-1 && location[x-1] == 0) { //x-1
				q.offer(x-1);
				location[x-1] = location[x]+1; // +1sec
			}
			if(x+1 <= 100000 && location[x+1] == 0) { // x+1
				q.offer(x+1);
				location[x+1] = location[x]+1;
			}
			if(2*x <= 100000 && location[2*x] == 0) { // 2*x
				q.offer(2*x);
				location[2*x] = location[x]+1;
			}
		}
		return -1; // fail
	}
}

결과 및 평가

---

딱히 막 결과가 좋진 않다. 더 효율적인 방식이 있을텐데... 아무래도 빠른 시간을 찾는거니까 조건을 따져서 순간이동을 제일 많이 하고 도착할 수 있게 해주면 되지 않을까? BFS 공부 목적으로 푼거라 나중에 생각나면 시도해야겠다.