/ BOJ

BOJ_1697_숨바꼭질_JAVA

문제 : 숨바꼭질

링크 : BOJ_1697_숨바꼭질

접근 방식

좌표를 x 한 가지만 사용하는 BFS 탐색 문제이다. 이 문제는 처음에 BFS를 사용하지 않고 풀어보려 했지만 조건문이 너무 복잡해져서 포기했다.

문제 자체는 간단하다 N과 K가 주어지고 N에서 +1 하거나, -1하거나 *2하여 K와 N을 같게 만드는 최소 시간을 구하면 된다. 따라서 BFS를 통해서 위의 연산을 계속해서 실행해주고, K의 위치에 처음 도착했을 때의 깊이가 최소시간이 된다.

풀이 방법

  1. BFS에 사용할 Node 클래스를 하나 만들었다. 멤버변수로는 x좌표와 bfs의 깊이를 담을 int변수가 있다.

  2. 주어진 값을 읽어들여 N과 K int형 변수에 저장한다.

  3. 주어진 방문 범위의 최댓값인 100001으로 생성하여 bfs에 인자값으로 넘겨 호출한다.

  4. BFS는 다른 문제와 유사하게 진행된다.

  5. N을 좌표로 하는 Node를 생성하여 Queue에 추가한다. visited 배열의 N번째 값을 방문처리한다.

  6. 큐가 전부 빌 때까지 반복한다. Queue에서 poll하여 노드에 할당한다.

  7. +연산, -연산 *2연산을 배열에 저장한다.

  8. 3번 반복하는데, 위의 연산을 한번 씩 실행하여 queue에 추가해준다. 해당 구문은 해당하는 값이 10만보다 작거나 같을 때, 또는 음수가 아닐 때, 그리고 해당 위치를 방문한 적이 없을 때에만 수행한다.

  9. 반복의 종료조건으로 큐에서 꺼낸 node의 좌표가 K와 같다면 해당 node의 깊이(depth)를 전역변수 cnt에 저장하고 return한다.

  10. bfs가 끝난 후, cnt값을 출력한다.

소스 코드


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

public class BOJ_1697_숨바꼭질 {
	static int N, K, cnt;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		N = Integer.parseInt(st.nextToken());

		K = Integer.parseInt(st.nextToken());

		bfs(new boolean[100001]);
		System.out.println(cnt);

	}

	static void bfs(boolean[] visited) {

		Queue<Node2> queue = new LinkedList<>();

		queue.offer(new Node2(N, 0));
		visited[N] = true;
		while (!queue.isEmpty()) {

			Node2 node = queue.poll();

			if (node.x == K) {
				cnt = node.depth;
				return;
			}


			int[] next = { node.x -1, node.x + 1, node.x*2 };

			for (int i = 0; i < 3; i++) {
				// 범위 체크 확실히 하자
				if (next[i] <= 100000 && next[i] >= 0 && !visited[next[i]]) {
					visited[next[i]] = true;
					queue.offer(new Node2(next[i], node.depth + 1));
				}
			}
		}
	}
}

class Node2 {

	int x;
	int depth;

	public Node2(int x, int depth) {
		super();
		this.x = x;
		this.depth = depth;
	}
}


// 경우의수 따지기 실패
//while(N != K) {
//	// N이 K보다 크면 N--
//	if(N > K) {
//		N--;
//	}
//	// N*2배가 K보다 작으면 무조건 2배
//	else if(N*2 < K ) {
//		N = N *2;
//	//	N*2가  K까지의 거리보다 크면서 N*2보다 N+1에서 K까지의 거리가 더 멀 때
//	}else if(N*2 > K) {
//		int M = N*2-K;
//		int temp = N;
//		int incnt = 0;
//		while(true) {
//			if(temp*2 - K > 2) {
//				temp--;
//				incnt++;
//			}else {
//				if(incnt < M) {
//					cnt = cnt + incnt;
//					N = temp;
//				}else {
//					N = N*2;
//				}
//				break;
//			}
//		}
//		N = N * 2;
// N*2가 K까지 거리보다 크지만 N+1에서 K까지의 거리가 더 가까울때

//	System.out.println(N);