작성 코드(DFS)
import java.io.*;
import java.util.*;
public class A_change_B_16953 {
static int minCnt = Integer.MAX_VALUE; // 최솟값을 저장할 전역 변수
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());
bfs(start, end, 0); // 초기 count 값을 0으로 전달
if (minCnt == Integer.MAX_VALUE) {
System.out.println(-1); // 만들 수 없는 경우
} else {
System.out.println(minCnt + 1); // 최솟값에 1을 더한 결과 출력
}
}
private static void bfs(long start, long end, int count) {
if (start == end) {
minCnt = Math.min(minCnt, count); // 최솟값 갱신
return;
}
if (start > end) {
return;
}
bfs(start * 2, end, count + 1); // 2를 곱하는 경우
bfs(start * 10 + 1, end, count + 1); // 가장 오른쪽에 1을 추가하는 경우
}
}설명
자료구조 및 로직
주어진 코드는 DFS(Depth-First Search) 알고리즘을 사용하여 시작 숫자 start를 목표 숫자 end로 변환하는 최소 횟수를 계산하는 프로그램입니다.
아래는 주요 코드 블록의 설명입니다.
-
main 함수:
- 입력을 받기 위해 BufferedReader와 StringTokenizer를 사용합니다.
- 시작 숫자 start와 목표 숫자 end를 입력받습니다.
- dfs 함수를 호출하여 시작 숫자를 목표 숫자로 변환하는 최소 횟수를 계산합니다.
- 계산된 최소 횟수를 출력합니다.
-
dfs 함수:
- 재귀적인 DFS 알고리즘을 구현한 함수입니다.
-
start와 end가 같은 경우:
- 현재까지의 탐색 횟수 count를 minCnt와 비교하여 더 작은 값으로 업데이트합니다.
- 함수를 종료합니다.
-
start가 end보다 큰 경우:
- 목표 숫자에 도달할 수 없으므로 함수를 종료합니다.
-
재귀 호출:
- start를 2배로 증가시킨 값을 dfs 함수에 재귀 호출합니다. 동시에 count를 1 증가시킵니다.
- start에 1을 추가한 뒤 10을 곱한 값을 dfs 함수에 재귀 호출합니다. 마찬가지로 count를 1 증가시킵니다.
- 코드는 시작 숫자 start에서 목표 숫자 end로 변환하기 위해 가능한 모든 경우를 탐색하며, DFS 알고리즘을 사용하여 깊이 우선적으로 탐색합니다. 최종적으로 최소 횟수를 minCnt 변수에 저장하고 출력합니다. 변환할 수 없는 경우에는 -1을 출력합니다.
이러한 방식으로 DFS 알고리즘을 활용하여 시작 숫자를 목표 숫자로 변환하는 최소 횟수를 계산할 수 있습니다.
자바스크립트(DFS)
let minCnt = Infinity;
function dfs(start, end, count) {
if (start === end) {
minCnt = Math.min(minCnt, count);
return;
}
if (start > end) {
return;
}
dfs(start * 2, end, count + 1);
dfs(start * 10 + 1, end, count + 1);
}
const input = require('readline-sync').question;
const st = input().split(' ');
const start = parseInt(st[0]);
const end = parseInt(st[1]);
dfs(start, end, 0);
if (minCnt === Infinity) {
console.log(-1);
} else {
console.log(minCnt + 1);
}파이썬(DFS)
minCnt = float('inf')
def dfs(start, end, count):
global minCnt
if start == end:
minCnt = min(minCnt, count)
return
if start > end:
return
dfs(start * 2, end, count + 1)
dfs(start * 10 + 1, end, count + 1)
st = input().split(' ')
start = int(st[0])
end = int(st[1])
dfs(start, end, 0)
if minCnt == float('inf'):
print(-1)
else:
print(minCnt + 1)작성 코드(BFS)
import java.io.*;
import java.util.*;
public class A_change_B_16953 {
static class Node {
long value;
int count;
public Node(long value, int count) {
this.value = value;
this.count = count;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long start = Long.parseLong(st.nextToken());
long end = Long.parseLong(st.nextToken());
int minCount = bfs(start, end);
if (minCount == -1) {
System.out.println(-1); // 만들 수 없는 경우
} else {
System.out.println(minCount + 1); // 최솟값에 1을 더한 결과 출력
}
}
private static int bfs(long start, long end) {
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(start, 0));
while (!queue.isEmpty()) {
Node node = queue.poll();
long value = node.value;
int count = node.count;
if (value == end) {
return count;
}
if (value < end) {
queue.offer(new Node(value * 2, count + 1)); // 2를 곱하는 경우
queue.offer(new Node(value * 10 + 1, count + 1)); // 가장 오른쪽에 1을 추가하는 경우
}
}
return -1; // 만들 수 없는 경우
}
}설명
자료구조 및 로직
주어진 코드에서 사용된 BFS(Breadth-First Search) 자료구조는 큐(Queue)입니다. 큐는 선입선출(FIFO, First-In-First-Out) 원칙에 따라 동작하는 자료구조로, 너비 우선 탐색에 적합합니다.
아래는 주어진 코드에서 사용된 BFS 자료구조의 구체적인 설명입니다:
-
static class Node
- Node는 큐에 저장되는 각 노드를 표현하는 내부 클래스입니다.
- Node 클래스는 value와 count라는 두 가지 속성으로 구성됩니다.
- value: 정수 값을 나타냅니다. 이 값은 현재 상태의 숫자를 의미합니다.
- count: 시작 값에서 현재 값까지의 연산 횟수를 나타냅니다.
-
private static int bfs(long start, long end)
- bfs 메서드는 주어진 시작 값 start와 목표 값 end를 기반으로 BFS를 수행합니다.
- BFS 알고리즘은 큐를 사용하여 탐색을 진행합니다.
- 먼저,
Queue<Node> queue = new LinkedList<>()를 사용하여 큐를 생성합니다. - 시작 값인 start를 초기 노드로 생성하여 큐에 추가합니다: queue.offer(new Node(start, 0)).
- 큐가 빌 때까지 다음 과정을 반복합니다.
- 큐에서 노드를 꺼내고, 해당 노드의 값을 value로, 연산 횟수를 count로 가져옵니다.
- value가 end와 같으면 count를 반환하고 BFS 탐색을 종료합니다.
- value가 end보다 작은 경우, value 2와 value 10 + 1을 각각 큐에 새로운 노드로 추가합니다.
- 큐를 모두 탐색한 후에도 end를 만들 수 없는 경우 -1을 반환합니다.
이렇게 구현된 BFS 자료구조를 사용하여 너비 우선 탐색을 수행하면, 시작 값에서 목표 값까지의 최소 연산 횟수를 찾을 수 있습니다. BFS는 큐를 활용하여 레벨 단위로 탐색하기 때문에 가장 빠른 경로를 찾는 데 유용한 알고리즘입니다.
자바스크립트(BFS)
class Node {
constructor(value, count) {
this.value = value;
this.count = count;
}
}
function bfs(start, end) {
let queue = [];
queue.push(new Node(start, 0));
while (queue.length > 0) {
let node = queue.shift();
let value = node.value;
let count = node.count;
if (value === end) {
return count;
}
if (value < end) {
queue.push(new Node(value * 2, count + 1)); // 2를 곱하는 경우
queue.push(new Node(value * 10 + 1, count + 1)); // 가장 오른쪽에 1을 추가하는 경우
}
}
return -1; // 만들 수 없는 경우
}
const input = require('readline-sync').question;
const st = input().split(' ');
const start = BigInt(st[0]);
const end = BigInt(st[1]);
const minCount = bfs(start, end);
if (minCount === -1) {
console.log(-1); // 만들 수 없는 경우
} else {
console.log(minCount + 1); // 최솟값에 1을 더한 결과 출력
}파이썬(BFS)
class Node:
def __init__(self, value, count):
self.value = value
self.count = count
def bfs(start, end):
queue = []
queue.append(Node(start, 0))
while queue:
node = queue.pop(0)
value = node.value
count = node.count
if value == end:
return count
if value < end:
queue.append(Node(value * 2, count + 1)) # 2를 곱하는 경우
queue.append(Node(value * 10 + 1, count + 1)) # 가장 오른쪽에 1을 추가하는 경우
return -1 # 만들 수 없는 경우
st = input().split(' ')
start = int(st[0])
end = int(st[1])
minCount = bfs(start, end)
if minCount == -1:
print(-1) # 만들 수 없는 경우
else:
print(minCount + 1) # 최솟값에 1을 더한 결과 출력
필요하다면 공부하는 개발자, 한승준