[프로그래머스/Lv.2] 숫자 변환하기 - Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

리뷰

프로그래머스 알고리즘 고득점 Kit에서 DFS/BFS 문제로 분류되는 타겟넘버와 비슷하다고 생각해서 아이디어를 얻었다.

풀이

Case #1 BFS

문제에 따라 x에서 n을 더한 경우, 2를 곱한 경우, 3을 곱한 경우를 모두 찾으면 위와 같은 그래프를 그릴 수 있을 것이다.

이를 탐색하면서 y가 되는 경우를 찾아 그 깊이를 구하면 된다.

 

이때 포인트는 불필요한 탐색을 하지 않도록 하는 것이다. 불필요한 탐색을 하지 않도록 만드는 조건은 두 가지를 고려하면 된다.

• 이미 탐색한 값을 중복 탐색하지 않는다.
• 목표(y)보다 큰 값을 탐색하지 않는다.

이 예시의 경우, depth 1에서 값 20을 탐색했다. 따라서 depth 2의 값 20을 중복 탐색하지 않도록 한다. 또한 depth 2의 값 45는 y인 40보다 크므로 탐색하지 않는다.

중복 탐색을 방지하기 위해 이전에 탐색한 값은 따로 기록했다. 이때 ArrayList를 사용할 경우 탐색 여부를 확인할 때 시간 초과가 발생하니 HashSet을 사용했다.

 

코드

import java.util.*;

class Solution {

    // 깊이를 정수 최대 값으로 지정한다.
    int min = Integer.MAX_VALUE;

    // 방문 여부를 탐색할 때 탐색 시간 줄이기 위해 HashSet 자료구조를 이용한다.
    Set<Integer> visited = new HashSet<>(); 

    public int solution(int x, int y, int n) {
        int answer = 0;

        bfs(x, y, n);        
        if(min == Integer.MAX_VALUE){
            answer = -1;
        }
        else {
            answer = min;
        }

        return answer;
    }

    private void bfs(int x, int y, int n) {        
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{x, 0});

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int v = cur[0];
            int depth = cur[1];

            // 목표값 y에 도달한 경우
            if (v == y) {
                min = depth;
                return;
            }

            int[] nexts = new int[]{v+n, v*2, v*3};
            for(int next: nexts){
                if(next > y){
                    continue;
                }

                // 한 번 도달해 본 숫자는 다시 쓰지 않는다.
                if(!visited.contains(next)) {
                    visited.add(next);
                    queue.offer(new int[]{next, depth+1});
                }
            }
        }

        return;
    }
}