05-15 08:39
Recent Posts
Recent Comments
Tags
- JOBνκ³
- TSQL
- DB
- νμ΄μ¬
- νμ΄μ곡λͺ¨μ
- μ€ν½μ€λΉ
- νλ‘λ³΄λ Έ
- μ¨μΌλν
- ICTλ©ν λ§
- μλ°
- mysql
- Spring
- νμ΄μ
- Naver Cloud
- DATABASE
- python
- RaspberryPi
- APIλ§μΌνλ μ΄μ€
- μλμ΄λ Έ
- μ€ν½λ ν
- μ΄λΈμ
- linux
- ICT
- μ‘νκ³
- appetizer
- API MarketPlace κΈλ‘λ² μν¬ν°μ¦
- ict곡λͺ¨μ
- SQL
- λ°μ΄ν°λ² μ΄μ€
- Java
- Today
- Total
miinsun
[BAEKJOON] λ°±μ€ BFS 12851 :: μ¨λ°κΌμ§ 2 λ³Έλ¬Έ
π¬ λ¬Έμ μ€λͺ
μλΉμ΄λ λμκ³Ό μ¨λ°κΌμ§μ νκ³ μλ€. μλΉμ΄λ νμ¬ μ N(0 ≤ N ≤ 100,000)μ μκ³ , λμμ μ K(0 ≤ K ≤ 100,000)μ μλ€. μλΉμ΄λ κ±·κ±°λ μκ°μ΄λμ ν μ μλ€. λ§μ½, μλΉμ΄μ μμΉκ° XμΌ λ κ±·λλ€λ©΄ 1μ΄ νμ X-1 λλ X+1λ‘ μ΄λνκ² λλ€. μκ°μ΄λμ νλ κ²½μ°μλ 1μ΄ νμ 2*Xμ μμΉλ‘ μ΄λνκ² λλ€.
μλΉμ΄μ λμμ μμΉκ° μ£Όμ΄μ‘μ λ, μλΉμ΄κ° λμμ μ°Ύμ μ μλ κ°μ₯ λΉ λ₯Έ μκ°μ΄ λͺ μ΄ νμΈμ§ κ·Έλ¦¬κ³ , κ°μ₯ λΉ λ₯Έ μκ°μΌλ‘ μ°Ύλ λ°©λ²μ΄ λͺ κ°μ§ μΈμ§ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
π¨ μ μΆλ ₯ μ
μ λ ₯
- 첫 λ²μ§Έ μ€μ μλΉμ΄κ° μλ μμΉ Nκ³Ό λμμ΄ μλ μμΉ Kκ° μ£Όμ΄μ§λ€. Nκ³Ό Kλ μ μμ΄λ€.
μΆλ ₯
- 첫째 μ€μ μλΉμ΄κ° λμμ μ°Ύλ κ°μ₯ λΉ λ₯Έ μκ°μ μΆλ ₯νλ€.
- λμ§Έ μ€μλ κ°μ₯ λΉ λ₯Έ μκ°μΌλ‘ μλΉμ΄κ° λμμ μ°Ύλ λ°©λ²μ μλ₯Ό μΆλ ₯νλ€.
μμ μ λ ₯ 1)
5 17
μμ μΆλ ₯ 1)
4
2
β
π» Main.java
μλΉμ΄μ νμ¬ μμΉκ° 5μ΄κ³ , λμμ μμΉκ° 17μΌ λ λ€μκ³Ό κ°λ€.
nμμ n-1, n+1,n*2 3κ°μ§ λ°©λ²μΌλ‘ λ»μ΄λκ°λ€κ³ μκ°ν΄λ³΄μ. BFSλ₯Ό μ΄μ©ν΄ λ¬Έμ λ₯Ό νμ΄ν΄λ΄€λ€.
4μμ 3, 5,8λ‘ λ»μ΄κ°λ 5λ μ΄λ―Έ level1μμ λμκΈ° λλ¬Έμ level2μμ 5λ₯Ό λ°©λ¬Έν νμκ° μλ€. (μ¦ 5λ 1μ΄λ©΄ λλ¬κ°λ₯νκΈ° λλ¬Έμ 2μ΄μ κ±Έμ³ 5λ₯Ό λ°©λ¬Έν νμκ° μλ€λ λ») 3μμ 2,4,6μΌλ‘ λ»μ΄λκ° λλ λ€μκ³Ό κ°μ μ΄μ λ‘ 4, 6μ λ°©λ¬Ένμ§ μμλ λλ€.
/* λ°±μ€ - 12851 :: μ¨λ°κΌμ§ 2 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
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[] min = new int[100001];
Queue<Integer> q = new LinkedList<>();
q.add(n);
min[n] = 1;
int cnt = 0;
while(!q.isEmpty()) {
int cur = q.poll();
// λμμ λ§λλ©΄ μΉ΄μ΄νΈ μ¦κ°
if(cur == k)
cnt++;
// μμΌλ‘ νμΉΈ κ±Έμ΄κ°κΈ°
if(cur - 1 >= 0 && cur - 1 <= 100000) {
if(min[cur - 1] == 0 || min[cur - 1] >= min[cur] + 1) {
min[cur - 1] = min[cur] + 1;
q.add(cur - 1);
}
}
// λ€λ‘ νμΉΈ κ±Έμ΄κ°κΈ°
if(cur + 1 >= 0 && cur + 1 <= 100000) {
if(min[cur + 1] == 0 || min[cur + 1] >= min[cur] + 1) {
min[cur + 1] = min[cur] + 1;
q.add(cur + 1);
}
}
// μκ°μ΄λ
if(cur * 2 >= 0 && cur * 2 <= 100000) {
if (min[cur * 2] == 0 || min[cur * 2] >= min[cur] + 1) {
min[cur * 2] = min[cur] + 1;
q.add(cur * 2);
}
}
}
System.out.println(min[k] - 1);
System.out.println(cnt);
br.close();
}
}
'Algorithm > Baekjoon' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BAEKJOON] λ°±μ€ κ·Έλν 3190 :: λ± (0) | 2022.07.14 |
---|---|
[BAEKJOON] λ°±μ€ BFS 14497 :: μ£Όλμ λ (0) | 2022.07.09 |
[BAEKJOON] λ°±μ€ BFS 2636 :: μΉμ¦ (0) | 2022.06.15 |
[BAEKJOON] λ°±μ€ BFS 2589 :: λ³΄λ¬Όμ¬ (0) | 2022.06.15 |
[BAEKJOON] λ°±μ€ κ·Έλ¦¬λ 10709 :: κΈ°μμΊμ€ν° (0) | 2022.06.13 |
Comments