[백준 / JAVA] 1697. 숨바꼭질

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

1697번: 숨바꼭질

 

---

💻 풀이 결과

 

💯 최종 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();

		Queue<Integer> queue = new LinkedList<>();
		// 시간 초과 + 메모리 초과 : 방문처리 배열을 만들어주어야한다.
		boolean[] visited = new boolean[100001];

		queue.add(N);
		visited[N] = true;

		int cnt = -1; // 수빈이 위치를 뽑는 것부터 시작점이기 때문
		while (!queue.isEmpty()) {
			int size = queue.size();
			cnt++;

			for (int s = 0; s < size; s++) {
				int curr = queue.poll();

				if (curr == K) {
					System.out.println(cnt);
					queue.clear();
					break;
				}

				// 걷기 or 순간이동
				int bWalk = (curr - 1);
				int fWalk = (curr + 1);
				int move = (curr * 2);
				// 조건 : visited 배열에 속하고 방문하지 않은 점일 때
				if (bWalk >= 0 && bWalk <= 100000 && !visited[bWalk]) {
					queue.add(bWalk);
					visited[bWalk] = true;
				}
				if (fWalk >= 0 && fWalk <= 100000 && !visited[fWalk]) {
					queue.add(fWalk);
					visited[fWalk] = true;
				}
				if (move >= 0 && move <= 100000 && !visited[move]) {
					queue.add(move);
					visited[move] = true;
				}
			} // for문 끝
		} // while문 끝
	}
}

 

💢 틀린 이유

1. 시간 초과

• 수빈이가 이동한 위치에 대한 방문 처리를 해주지 않아 시간 초과가 발생하였다.
• visited 정수형 배열을 생성하여 해결했는데, N의 범위가 100,000 이하이므로 100,001 크기로 만들었다.

2. 메모리 초과

• 넉넉한 크기의 visited 배열을 만들기 위해 200,001 크기의 배열을 만들었는데, 가장 빠른 시간을 찾는 것이기 때문에 굳이 그렇게 만들 필요가 없었다. (100,000을 넘어서서 -1을 계속해야 한다면 최소 시간이 될 수는 없다.)
• 처음에 방문 검사를 해주지 않고 큐에 삽입하면서 메모리 초과가 발생한 것 같아, 방문 검사를 하여 큐에 방문했던 점의 위치가 쌓이는 것을 막았다.

💬 풀이 과정

• 수빈이의 아래로 걷기, 위로 걷기, 순간 이동 각각의 위치들을 BFS를 돌리면서 큐에 저장하였다.
• 큐에서 뽑았을 때 동생의 위치와 같다면 큐를 비우고 while문을 종료시켰다.

💡 깨달은 점

1. BFS 응용 - 1차원에서의 BFS

• 2차원 배열에서의 BFS와 동일하게 생각하면 된다.
• 1차원이라고 해서 방문 처리가 필요 없다는 안일한 생각은 하면 안 된다..