728x90
문제
풀이
문제에 주어진 최대값(100,000)의 Integer 배열(check)을 생성한다.
수빈이(N)와 동생(K)의 위치를 입력받는다.
queue를 생성하고 N을 추가한다.
check[N] 값을 1로 입력한다.
queue가 비어있을 때까지 반복하며 queue에서 값(q)을 꺼낸다.
3번 반복하며 q + 1, q - 1, q * 2 값(next)을 구한다.
next가 K인 경우 check[q]를 출력한다.
next가 최대값보다 작고, 0보다 같거나 크고, check[next]에 값이 0인 경우
check[q] + 1을 check[next]에 입력한다.
정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N;
static int K;
static Queue<Integer> queue = new LinkedList<>();
static int[] check = new int[100001];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
queue.add(N);
// N이 K인 경우
if (N == K) {
System.out.println(0);
} else {
queue.add(N);
check[N] = 1;
bfs();
}
}
static void bfs() {
while(!queue.isEmpty()) {
int q = queue.poll();
for (int i = 0; i < 3; i++) {
int next;
if (i == 0) {
next = q + 1;
} else if (i == 1) {
next = q - 1;
} else {
next = q * 2;
}
if (next == K) {
System.out.println(check[q]);
return;
}
// next가 범위 내이고 아직 방문하지 않은 경우
if (next >= 0 && next < check.length && check[next] == 0) {
queue.add(next);
check[next] = check[q] + 1;
}
}
}
}
}
문의사항이나 피드백은 댓글로 남겨주세요.
'백준' 카테고리의 다른 글
[백준] 2468번: 안전 영역 - JAVA (0) | 2025.02.05 |
---|---|
[백준] 5014번: 스타트링크 - JAVA (0) | 2025.02.05 |
[백준] 7569번: 토마토 - JAVA (0) | 2025.02.05 |
[백준] 2644번: 촌수계산 - JAVA (1) | 2025.02.05 |
[백준] 1012번: 유기농 배추 - JAVA (0) | 2025.02.05 |