bfs로 count를 구하는 문제
bfs: queue를 이용하여 count 구하기 쉬움
dfs: 재귀 함수로 구현되기에 count 구하기 쉽지 않음
예시 : 수빈이 N - 5, 동생 K - 17
0초
1초
2초
3초
4초에 17 도달
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int count =0;
if(N==K){
System.out.print(0);
return;
}
boolean[] visited= new boolean[100001];
Queue<Integer> q = new LinkedList<>();
q.add(N);
int size = q.size();
while(true){
count++;
size = q.size();
for (int i=0;i<size;i++){
int x = q.poll();
if(x-1==K||x+1==K||2*x==K){
System.out.print(count);
return;
}if(x-1>0&&!visited[x-1]){
visited[x-1] = true;
q.add(x-1);
}if(x+1<=100000&&!visited[x+1]){
visited[x+1] = true;
q.add(x+1);
}if(x*2<=100000&&!visited[2*x]){
visited[2*x] = true;
q.add(2*x);
}
}
}
}
}
오늘의 회고
- 문제에 맞는 알고리즘을 정확히 떠올려서 풀자 아니면 시간낭비..!
- 내일(4/10) 학습 예정 : bfs/dfs 알고리즘 공부
'algorithm > 문제 풀이' 카테고리의 다른 글
99클럽 코테 스터디 11일차 TIL - 백준 14888 (연산자 끼워넣기) (0) | 2024.04.11 |
---|---|
99클럽 코테 스터디 10일차 TIL - 프로그래머스 이진 변환 반복하기 (0) | 2024.04.10 |
99클럽 코테 스터디 8일차 TIL - 백준 1931 (회의실배정) (0) | 2024.04.08 |
백준 1654번 (랜선 자르기) 자바 Java (0) | 2024.04.07 |
백준 10974번 (모든 순열) 자바 Java (0) | 2024.04.06 |