https://school.programmers.co.kr/learn/courses/30/lessons/154538
👀 핵심개념
문제는 x에서 y로가는 연산의 최소 횟수를 구하는 문제이니 너비우선탐색(BFS)를 적용해서 구할 수 있습니다. 그리고 특정 숫자에서 해당 연산을 진행했는지 여부까지 확인해주면 됩니다.
깊이 우선탐색(DFS)도 좋은 문제를 찾으면 포스팅 진행 예정입니다.
🎈 코드
class Solution {
public int solution(int x, int y, int n) {
int answer = 0; // 정답을 저장할 변수, 몇 번의 연산을 통해 y에 도달하는지 계산
Queue<Integer> queue = new LinkedList<>(); // BFS 탐색을 위한 큐
Set<Integer> set = new HashSet<>(); // 중복 계산을 방지하기 위한 집합 (이미 방문한 숫자들을 저장)
queue.add(x); // 시작값 x를 큐에 추가
while (!queue.isEmpty()) { // 큐가 비어있지 않은 동안 반복
int size = queue.size(); // 현재 큐에 들어있는 요소의 수를 확인 (현재 단계에서 탐색할 모든 요소들)
for (int i = 0; i < size; i++) { // 큐에 있는 모든 요소에 대해 탐색
int temp = queue.poll(); // 큐에서 요소를 하나 꺼냄
if (temp == y) return answer; // 꺼낸 요소가 y와 같으면, 답을 반환 (현재까지의 연산 횟수)
// 세 가지 연산을 통해 새로운 숫자를 큐에 추가
if (temp * 2 <= y && !set.contains(temp * 2)) {
queue.add(temp * 2);
set.add(temp * 2);
}
if (temp * 3 <= y && !set.contains(temp * 3)) {
queue.add(temp * 3);
set.add(temp * 3);
}
if (temp + n <= y && !set.contains(temp + n)) {
queue.add(temp + n);
set.add(temp + n);
}
}
answer++; // 큐에 있는 모든 요소를 처리한 후 연산 횟수를 증가
}
return -1; // 큐가 비었는데도 y에 도달하지 못한 경우, -1을 반환
}
}그냥 순회만 돌리면 한 숫자를 여러 방법을 통해 접근할 수 있으니 조건문을 통해 해당 값에 접근한 적이 있는지의 확인 여부와 값이 무한대로 증가하지 않기 위해 y를 넘지 않도록 조건문을 통해 연산 불가능한 값은 -1에 도달할 수 있게 처리해주면됩니다 :)
