[백준] 1697 숨바꼭질 - Graph Theory / Java

• 문제 링크

1697번: 숨바꼭질

 

• 풀이 과정

너비 우선 탐색을 수행할 함수를 정의, 현재 위치(n) 와 도착 위치(k) 를 매개변수로 받고 큐에 현재 위치를 저장한다.

그리고 방문 여부를 확인할 chk 배열을 문제에 제시된 조건에 의해 100,001의  크기로 생성, 현재 위치를 1로 표시한다.

 

현재 위치는 loc 변수에, 다음으로 이동할 위치를 move 변수에 설정하며

3가지 이동 방법 (n + 1, n - 1, n * 2) 으로 이동한 모든 경우를 탐색하여 다음 이동할 위치가 지정된다.

 

다음 이동할 위치가 이동 가능한 범위를 벗어나지 않고 방문한 적이 없다면 큐에 넣어 현재 위치를 갱신한다.

만약 이동할 위치가 도착 위치, 즉 k 와 같다면 그대로 반복문을 빠져나와 결과 값으로써 반환한다.

 

• 풀이 코드

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;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		if (n == k)
			bw.write(0 + "\n");
		else
			bw.write(bfs(n, k) + "\n");

		bw.flush();
	}

	private static int bfs(int n, int k) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(n);

		int[] chk = new int[100001];
		chk[n] = 1;
		
		int result = 0;
		loop:
		while (!q.isEmpty()) {
			int loc = q.poll();
			for (int i = 0; i < 3; i++) {
				int move;

				if (i == 0)
					move = loc + 1;
				else if (i == 1)
					move = loc - 1;
				else
					move = loc * 2;

				if (move == k) {
					result = chk[loc];
					break loop;
				}

				if (move >= 0 && move < chk.length && chk[move] == 0) {
					q.offer(move);
					chk[move] = chk[loc] + 1;
				}
			}
		}

		return result;
	}

}