๐ ๏ธ ๋ฌธ์ ๐ ๏ธ
๐๏ธ ์ค๋ช ๐๏ธ
์ด๋ฒ ๋ฌธ์ ์์ ๋ด๊ฐ ์๋ชป ์๊ฐํ๋ ๋ถ๋ถ์ ๋ํด ๊ธฐ๋กํด๋๋ ค๊ณ ํ๋ค.
์ฐ์ ๊ธฐ์ตํด์ผํ ๊ฒ์ BFS๋ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ ์ ์๋ค.
์ฆ, ์ฒ์ ๋์์ ์์น์ ๋์ฐฉํ๋ฉด(answer = 0) ๊ทธ ๋ ์๊ฐ์ด ์ต์์๊ฐ์ด ๋๋ค.
์ฌ๊ธฐ๊น์ง๋ง ์๊ฐํ๊ณ ์์ฑํ ์ฝ๋ ์ค queue ์ฝ์ ๊ณผ ๊ด๋ จ๋ ์ฝ๋์ด๋ค.
์์ ๊ฐ์ด ๋จ์ง next์์น์์ ๋๋ฌํ ์๊ฐ์ด ์ต์ ์๊ฐ๋ณด๋ค ์์ผ๋ฉด ๋ฌด์กฐ๊ฑด queue์ ๋ฃ๋๋ก ํ๋ค.
ํ์ง๋ง ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ฐ์ํ๊ณ ๊ทธ ์ด์ ์ ๋ํด ์๊ฐํด๋ณด์๋ค.
ํ์ฌ ์ฝ๋๋ก๋ ๋์ฐฉ์ง์ ๊ณผ ํ์ฌ ์ง์ ์ ๊ฑฐ๋ฆฌ์ ์๊ด์์ด ํ์ฌ ์๊ฐ์ด ์ต์ ์๊ฐ๋ณด๋ค ์์ผ๋ฉด ๋ฌด์กฐ๊ฑด ํ์ ์ฝ์ ํ๋ค.
๊ทธ๋ฌ๋ฉด ์ ๋ ์ต์์๊ฐ์ ๋์ฐฉํ ์ ์๋ ๊ฒฝ์ฐ๋ ํ์ ์กด์ฌํ๋ฉฐ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ฐ์ํ ์ ์๋ค.
์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด๋ณด๋ฉด queue์์ 1๊ฐ๋ฅผ ๋นผ๊ณ 3๊ฐ๊ฐ ๋ค์ด๊ฐ 2๊ฐ์ฉ ์์ด๋ ์ํฉ์ด ๊ณ์ ๋ฐ์ํ ๊ฒ์ด๋ค.
๋ง์ฝ ๋์๊ณผ ์๋น์ด์ ์์น๊ฐ ๋งค์ฐ ํฐ ์ฐจ์ด๋ฅผ ๊ฐ์ง๊ณ ์์ผ๋ฉด ๋น์ฐํ queue์ ๊ธธ์ด๋ ๋งค์ฐ ๊ธธ์ด์ง ๊ฒ์ด๋ค.
๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ ์ฌ์ฉํ๊ธฐ ์ํด ํ ์ ์๋ ๋ฐฉ๋ฒ์ ํ์ ์ฝ์ ํ๋ ์กฐ๊ฑด์ ์ถ๊ฐํด์ฃผ๋ ๊ฒ์ด๋ค.
๋์ฐฉ ์ง์ ๋ฟ๋ง ์๋๋ผ ํ์ฌ ์์น๊น์ง๋ ์ต์ ์๊ฐ์ผ๋ก ๋๋ฌํด์ผ ๋์ฐฉ๊น์ง ์ต์ ์๊ฐ์ด ๊ฑธ๋ฆด ๊ฐ๋ฅ์ฑ์ด ์๋ค.
์ฆ, ํ์ฌ ์์น๊น์ง ์ด๋ค ๋ฐฉ์์ผ๋ก ๋๋ฌํ๋๋ผ๋ ์ต์ ์๊ฐ์ด๊ธฐ๋ง ํ๋ฉด ๋๋ค๋ ๊ฒ์ด๋ค.
visited ๋ฐฐ์ด์ ๋ง๋ค์ด ํ์ฌ ์ ์ ์ ๋๋ฌํ๋ ์ต์ ์๊ฐ์ ๊ธฐ๋กํด๋ ์ ์๋๋ก ํ๋ค.
์์์ BFS์ ํน์ฑ์ ๋งํ๋ฏ์ด ํ์ฌ ์ ์ ์ ๋๋ฌํ ์๊ฐ ๊ทธ ์๊ฐ์ด ์ต์์๊ฐ์ด ๋ ๊ฒ์ด๋ค.
visited = 0์ผ ๊ฒฝ์ฐ ๋ฐฉ๋ฌธ ํ์ง ์์์ผ๋ฏ๋ก ํ์ฌ ๋์ฐฉํ ์๊ฐ์ด ์ต์์๊ฐ์ด ๋๋ฏ๋ก ์ด๋ฅผ ๊ธฐ๋กํด๋๋ก ํ๋ค.
์ฌ๋ฐฉ๋ฌธํ ๋(visited != 0) ํ์ฌ ์ ์ฅ๋์ด ์๋ ์ต์ ์๊ฐ์ ๋๋ฌํ์ ๊ฒฝ์ฐ์๋ง ํ์ ์ฝ์ ํ๋๋ก ํ์ฌ ์ฝ์ ์กฐ๊ฑด์ ์ถ๊ฐํ๋ค.
๐ ํ์ด ๐
package Baekjoon;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Graph12851 {
public static class Node {
int x, time;
public Node(int x, int time) {
this.x = x;
this.time = time;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
if(start >= end) { //๋ง์ฝ ์๋น์ด๊ฐ ๋์๋ณด๋ค ์์ ์์ ๊ฒฝ์ฐ ๋ค๋ก๋ง ๊ฐ๋ ๋ฐฉ์์ผ๋ก ๋์ฐฉ
System.out.println(start-end);
System.out.println(1);
return;
}
bfs(start, end);
}
/**
* ์ต์ ์๊ฐ๊ณผ ๋ฐฉ๋ฒ์ ๊ฐ์ ์ถ๋ ฅํ๋ ํจ์
* @param s ์๋น์ด์ ์์ ์์น
* @param e ๋์์ด ์๋ ๋์ฐฉ ์์น
*/
public static void bfs(int s, int e) {
int answer = 0;
int minTime = Integer.MAX_VALUE;
int[] visited = new int[100001];
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(s, 0));
while(!queue.isEmpty()) {
Node current = queue.poll();
if(minTime < current.time) {
continue;
}
if(current.x == e) {
if(answer == 0) { //BFS๋ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๊ธฐ ๋๋ฌธ์ ์ฒ์์ ๋๋ฌํ ๊ฒฝ์ฐ๊ฐ ์ต์ ์๊ฐ
minTime = current.time;
}
if(current.time == minTime) {
answer++;
continue;
}
}
int[] next = {current.x-1, current.x+1, current.x*2};
for(int i = 0; i < 3; i++) {
if(next[i] < 0 || next[i] > 100000) {
continue;
}
//0์ผ ๊ฒฝ์ฐ ๋ฐฉ๋ฌธํ ์ ์ด ์์ผ๋ฏ๋ก ํ์ฌ ์๊ฐ์ด ์ต์ ์๊ฐ
//ํ์ฌ ์ ์ ์ ์ต์์๊ฐ์ผ๋ก ๋๋ฌํด์ผ ๋์์ ์์น๊น์ง ์ต์๋ก ์ฌ์ ์๋ ๊ฐ๋ฅ์ฑ ์กด์ฌ
if(visited[next[i]] == 0 || visited[next[i]] == current.time + 1) {
visited[next[i]] = current.time + 1;
queue.offer(new Node(next[i], current.time+1));
}
}
}
System.out.println(minTime);
System.out.println(answer);
}
}
'ProgramSolve > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] 11779๋ฒ - ์ต์๋น์ฉ ๊ตฌํ๊ธฐ2 (Java) (2) | 2023.12.08 |
---|---|
[BOJ] 13270๋ฒ - ํผ๋ณด๋์น ์นํจ (Java) (2) | 2023.12.06 |
[BOJ] 2437๋ฒ - ์ ์ธ (Python) (0) | 2023.10.27 |
[BOJ] 15657๋ฒ - N๊ณผM(8) (Python) (1) | 2023.10.05 |
[BOJ] 1911๋ฒ - ํ๊ธธ ๋ณด์ํ๊ธฐ (Python) (0) | 2023.09.07 |