[Java] BFS(Breadth-First Search) 알고리즘이란?

BFS(Breadth-First Search) 이란?

너비 우선 탐색이라고 불리며 그래프 자료구조에서 완벽 탐색을 수행하는 탐색 기법이다.

시작부분인 노드에 방문한 후 인접한 노드들을 우선으로 방문하며 기본적으로는 Queue 자료 구조를 이용해서 구현한다.

---

특징

• 재귀적으로 동작하지 않는다.
• BFS도 DFS처럼 노드 방문 여부를 검사해야 한다.
• 최단경로를 찾는데 활용한다.

---

탐색 과정

 

 

1. 노드1 를 시작으로 자료구조에 데이터를 넣으면서 시작한다.
2. 노드1를 진행하고 방문완료 처리 후 노드1에서 파생되는 노드2와 노드3를 자료구조에 넣는다.
3. 2번 과정에 의해 노드2가 먼저 자료구조에 들어갔기에 노드2를 진행하며 노드2 또한 진행하고 방문완료 처리 후 노드 2에서 파생되는 노드4와 노드5를 자료구조에 넣는다.
4. 노드3를 진행하고 방문완료 처리 후 노드3에서 파생되는 노드6를 자료구조에 넣는다.
5. 그리고 순서대로 노드4 , 노드5 , 노드6를 진행하고 노드6에서 파생되는 노드7를 자료구조에 넣는다.
6. 마지막으로 노드7를 완료하고 종료

---

문제 적용

프로그래머스 숫자 변환하기 문제를 풀다가 BFS 알고리즘을 적용해서 풀어보았다.

 

문제 설명

주어진 값이 총 3개가 있다. x , y , n 여기서 각자 의미하는 것은 아래와 같다.

x = 시작값

y = 도달해야하는 값

n = 더하는 값

위 3개의 값으로 사용할수 있는 연산을 기반으로 최소 횟수만에 x를 y에 맞게 만들면 된다.

 

사용할수 있는 연산

• x + n
• x * 2
• x * 3

 

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

 

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

 

풀이과정

BFS 알고리즘을 이용해서 풀었다. 다만... Queue가 아닌 Map를 이용해서 비스무리하게 구현했다.

입출력 예 #1 기준으로 그림을 그려본다.

이 흐름대로 파생되는 값을 계속 자료구조에 넣으면서 반복문을 계속 돌려서 최소 연산 수를 찾는다.

 

 

코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = -1;
        
        // Map<x로 만든 숫자 , 도달하는데 걸린 횟수>
        Map<Integer , Integer> map = new HashMap<>();
        map.put(x , 0);  // 처음은 <x , 0>으로 시작
        
        while (map.size() > 0) {
            // 정렬을 위한 리스트
            List<Integer> sortList = new ArrayList<>(map.keySet());
            Collections.sort(sortList);
            for (Integer idx : sortList) {
                // idx를 만드는데 카운트된 value값 꺼내기
                int value = map.get(idx);
                // idx를 진행함에 따라 remove
                map.remove(idx);
                
                // idx + n 이 y보다 같거나 작고 map에 존재하지 않으면!
                // 존재하지 않아야하는 이유는 먼저 존재하고 있다는 것은 
                // value값이 더 작다는 것을 의미
                if (idx + n <= y && !map.containsKey(idx + n)) {
                    map.put(idx + n , value + 1);
                }
                // idx * 2 이 y보다 같거나 작고 map에 존재하지 않으면!
                if (idx * 2 <= y && !map.containsKey(idx * 2)) {
                    map.put(idx * 2 , value + 1);
                }
                // idx * 3 이 y보다 같거나 작고 map에 존재하지 않으면!
                if (idx * 3 <= y && !map.containsKey(idx * 3)) {
                    map.put(idx * 3 , value + 1);
                }
            }
            
            // idx값이 y와 같다면 반환
            for (Integer idx : Set.copyOf(map.keySet())) {
                if (idx == y) {
                    return map.get(idx);
                }
            }
        }
        
        // 둘의 값이 같다면 0
        if (x == y) return 0;
        
        // x로 y를 만들어 낼수 없다면 -1
        return answer;
    }
}