백준 1697 숨바꼭질 (BFS)

1. 문제

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

 

2. 설명

늘 풀던 그 BFS 최단거리 방식으로 풀었다. 입력은 두개밖에 없어서 Scanner로 받았다.

 

3. 코드

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

public class Main {
	
	static void bfs(int n, int k) {
		Queue<Integer> q = new LinkedList<>();
		int[] cnt = new int[100001];
		q.add(n);
		
		while(!q.isEmpty()) {
			n = q.poll(); // 현재 수빈의 위치
			if(n==k)
				break;
			if(n+1<=100000 && cnt[n+1]==0) {
				q.add(n+1);
				cnt[n+1] = cnt[n] + 1;
			}
			if(n-1>=0 && cnt[n-1]==0) {
				q.add(n-1);
				cnt[n-1] = cnt[n] + 1;
			}
			if(n*2<=100000 && cnt[n*2]==0) {
				q.add(n*2);
				cnt[n*2] = cnt[n] + 1;
			}
		}
		System.out.println(cnt[n]);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 수빈
		int K = sc.nextInt(); // 동생
		
		bfs(N,K);
	}
}

원래는 아래와 같이 풀려고 했었는데, 위의 방법이 메모리나 시간적으로 아주 조금 더 좋더라

풀이 진행과정은 위 아래 둘다 같음.

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

public class Main {
	
	static void bfs(int n, int k) {
		Queue<Integer> q = new LinkedList<>();
		int[] cnt = new int[100001];
		int[] move = new int[3];
		q.add(n);
		
		while(!q.isEmpty()) {
			n = q.poll(); // 현재 수빈의 위치
			
			if(n==k)
				break;

			move[0] = n + 1;
			move[1] = n - 1;
			move[2] = n * 2;
			
			for(int i=0; i<3; i++) {
				if(move[i]>=0 && move[i]<=100000 && cnt[move[i]]==0) {
					q.add(move[i]);
					cnt[move[i]] = cnt[n] + 1;
				}
			}
		}
		System.out.println(cnt[n]);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 수빈
		int K = sc.nextInt(); // 동생
		
		bfs(N,K);
	}
}