코드 흐름
- 우선 문제를 보자마자 BFS가 떠올랐다. 오랜만의 BFS라 상당히 긴장되었고 Node라는 클래스를 따로 하나 만들어 그안에 숫자와 깊이를 저장할 수 있도록 하였다.
- Queue 하나와 isVisited 배열을 하나 선언하여 BFS의 구동 조건을 갖추었다.
- Queue 에 최초의 값 x와 깊이 0을 노드에 담아 집어 넣어주고 그 최초의 값으로 하여금 연산후 y보다 작고 이전에 이미 나왔던 값이 아니라면 연산과 isVisited 체크를 진행 해주었다.
- while 문에서 q에서 뽑아낸 node 속 숫자가 y에 도달한다면 x가 연산후 y에 도달했음을 체크하는 isValid를 true로 바꾸고 반복문을 종료한다.
import java.util.*;
class Node{
int num;
int depth;
public Node(int num,int depth){
this.num = num;
this.depth = depth;
}
}
class Solution {
public int solution(int x, int y, int n) {
int answer = 0;
boolean isValid = false;
Queue<Node> q = new ArrayDeque<>();
boolean[] isVisited = new boolean[1000001];
q.add(new Node(x,0));
isVisited[x]=true;
while(!q.isEmpty()){
Node node = q.poll();
if(node.num==y){
isValid=true;
answer = node.depth;
break;
}
if(node.num+n<=y && !isVisited[node.num+n]){
q.add(new Node(node.num+n,node.depth+1));
isVisited[node.num+n]=true;
}
if(node.num*2<=y && !isVisited[node.num*2]){
q.add(new Node(node.num*2,node.depth+1));
isVisited[node.num*2]=true;
}
if(node.num*3<=y && !isVisited[node.num*3]){
q.add(new Node(node.num*3,node.depth+1));
isVisited[node.num*3]=true;
}
}
return isValid?answer:-1;
}
}
'Algorithm > Programers' 카테고리의 다른 글
Lv 2. 프렌즈4블록 (0) | 2024.07.21 |
---|---|
Lv 2. 2xn타일링 (1) | 2024.07.20 |
Lv 2. 오픈채팅방 (0) | 2024.07.18 |
Lv 2. 택배상자 (1) | 2024.07.17 |
Lv 2. 스킬트리 (0) | 2024.07.14 |