[BOJ] 숨바꼭질

❗ 풀이 과정

• BFS를 활용해서 풀면 된다.
• 처음에 풀이할 때에는 queue에 다 집어넣고 완전탐색으로 풀면 되지 않을까? 했지만,, 메모리 초과가 났다
• visited 배열을 활용해, 방문한 위치는 다시 탐색하지 않도록 제한을 걸어두고 했더니 성공!

😥 메모리 초과 났던 코드

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();
		int cnt 	= 0;
		int result 	= 0;
		
		Queue<Integer> queue = new LinkedList<Integer>();
		if(N==K) {
			System.out.println(0);
		}
		else {
			queue.offer(N);				//enqueue
			while(queue.size()>0) {
				cnt++;				
				int tmp = queue.poll();	// dequeue
	
				if(tmp-1 == K || tmp+1 == K || tmp*2 == K) {
					break;
				}
				
				queue.offer(tmp-1);
				queue.offer(tmp+1);
				queue.offer(tmp*2);
			}

			// queue   3^0, 3^1, 3^2, 3^3, 3^4, ..
			int i=0;
			while(cnt>0) {
				result++;
				cnt-=Math.pow(3,i);
				i++;
			}
			System.out.println(result);
		}
		sc.close();
	}
}

🤜 풀이 코드

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

public class Main_1697_숨바꼭질 {
	public static void main(String[] args) {
		Scanner sc 	= new Scanner(System.in);
		int N 		= sc.nextInt();
		int K 		= sc.nextInt();
		int [] visited = new int [100001];			// 위치 방문 표시
		
		Queue<Integer> queue = new LinkedList<Integer>();
		
		visited[N]=1;	// 시간 표시 (1초 더 많게 표시 : 0 은 방문 안한 거 체크하려고)
		
		if(N==K) {
			System.out.println(0);
		}
		else {
			queue.offer(N);				//enqueue
			while(queue.size()>0) {			
				int tmp = queue.poll();	// dequeue
	
				if(tmp-1 == K || tmp+1 == K || tmp*2 == K) {
					System.out.println(visited[tmp]);
					break;
				}
				
				// index 밖에 나가지 않고 방문 안했는지 체크
				if(tmp-1>=0 && visited[tmp-1]==0) {		
					queue.offer(tmp-1);
					visited[tmp-1]=visited[tmp]+1;
				}
				if(tmp+1<100001 && visited[tmp+1]==0) {
					queue.offer(tmp+1);
					visited[tmp+1]=visited[tmp]+1;
				}
				if(tmp*2<100001 && visited[tmp*2]==0) {
					queue.offer(tmp*2);
					visited[tmp*2]=visited[tmp]+1;
				}
			}
		}
		sc.close();
	}
}