백준 - 1697

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int K;
	static boolean[] visited;
	static int[] distance;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		if (N == K) {
		    System.out.println(0);
		    return;
		}
		System.out.println(bfs(N));
	}
	static int bfs(int start) {
		
		visited = new boolean[100001];
		distance = new int[100001];
		
		Queue<Integer> q = new ArrayDeque<>();
		q.offer(start);
		visited[start] = true;
		
		while(!q.isEmpty()) {
			int n = q.poll();

			int[] over = {n+1, n-1, n * 2};
			
			for(int next : over) {
				if(next >= 0 && next <= 100000 && !visited[next]) {
					visited[next] = true;
					distance[next] = distance[n] + 1;
					
					if(next == K) return distance[next];
					q.offer(next);
					
				}
			}
		}
		return -1;
	}
}

풀이과정 및 리뷰

1. 우선 N / K 를 입력받은 후 bfs의 파라미터로 N을 넘김(int start)
2. 이때 N == K 라면 0을 리턴하고 바로 종료
3. bfs메서드 호출
   • 100,001개의 visited - 방문여부 체크 / distance - 해당 지점까지의 최단거리 저장하는 배열 선언
   • q에 시작점을 넣고 방문체크
   • 큐가 빌때까지 큐에서 데이터를 꺼내 n+1 / n-1 / 2 * n한 next 값들을 차례로 순회하며, 방문하지 않은 경우에 한해(인덱스초과 에러 방지 조건 추가) 미리 방문체크 및 최단 카운트 저장
   • next값을 큐에 저장해 연산 계속 수행
   • 이때, if(next == K) return distance[next] 코드가 존재하지 않아도 메인에서 sysout(distance[K] 로 값을 찾을 수 있음. → K에 도달하는 최단거리를 구하기 위해 bfs를 사용했는데, bfs는 인접노드부터 탐색하므로 next == K를 만나서 리턴해도 결과값은 같음
     

리뷰

if(next == K) return distance[next]

next == K일 때 바로 return 하는 건 BFS에서는 맞고, DFS에서는 틀릴 수 있다.

BFS (Breadth-First Search)

• 최단 거리 보장 O → 즉 처음 발견하는 순간이 최단거리
• 큐를 사용해서 레벨 순서대로 탐색
• 먼저 도착한 경로가 곧 최단 경로
• 그래서 next == K일 때 바로 리턴해도 안전

❌ DFS (Depth-First Search)

• 최단 거리 보장 안 됨 X → DFS에선 끝까지 다 탐색하고, 가장 짧은 거리만 골라야 함
• 스택 또는 재귀로 한쪽 끝까지 파고듦
• 먼저 도착한 경로가 최단일 가능성이 없음
• 그래서 next == K에서 바로 return 하면 틀릴 수 있음