BFS(너비 우선 탐색, 백준 알고리즘 16953번)

♣ 문제

 

♣ 문제 이해

 

주어진 정수 A를 정수 B로 바꾸는 문제로, A*2를 하거나 str(A)+'1'을 해서 숫자를 바꿔간다. 

첫 번째 예제를 보면

 

2 -> 4 -> 8 -> 81 -> 162 루트를 통해서 162를 만들 수 있고, 4번의 숫자 변화 끝에 답을 얻은 것이므로 4+1 = 5 를 프린트한다. 

 

반면 두 번째 예제(4, 42)를 보면

 

위의 그림과 같아서 4를 42로 만들 수 있는 경우가 없기 때문에 -1을 출력해야 한다. 

 

 

♣ 문제 해결 방법

처음에는 주어진 오리지널 숫자를 2배 하거나 뒤에 1을 덧붙이는 수를 모두 리스트에 넣어서 조건을 따지려고 했는데 너무 복잡하게 느껴졌다. 그래서 오리지널 숫자는 그냥 두고 원하는 결과인 숫자로부터 따지기로 했다. 

 

예를 들어 첫 번째 예제(2, 162)라면 162로부터 그 전으로 돌아가는 것이다. 하나의 숫자에 가할 수 있는 변화를 두 가지다. 

• 곱하기 2를 한다
• 맨 뒤에 1을 붙인다

그런데 162는 1로 끝나지 않는 수이므로 그 전 단계 숫자에 곱하기 2를 했을 것이다. 따라서 162의 전 숫자는 81이 된다. 

이제 81을 따진다. 81은 2의 배수가 아니므로 그 전 단계 숫자의 끝에 1을 더했을 것이다. 따라서 81의 전 숫자는 8이다.

8은 2의 배수이므로 전 숫자는 4이고, 4 역시 2의 배수이므로 전 숫자는 2이다. 드디어 오리지널 숫자인 2를 얻었다. 

따라서 2가 162로 변한 과정은 아래와 같다

 

2 -> 4 -> 8 -> 81 -> 162  

 

이 과정을 거꾸로 찾은 것이다. 

 

162 -> 81 -> 8 -> 4 -> 2

 

4번 만에 2가 되었으므로 +1을 하면 5를 출력할 수 있다. 

 

두 번째 예제(4, 42)라면 42로부터 4로 돌아갈 수 있어야 한다. 위와 똑같은 과정을 거치면

 

42 -> 21 -> 2 -> 1

 

4로 돌아갈 수 없으므로 -1을 출력해야 한다. 

 

 

♣ 문제 해결 코드

 

while 문을 넣고, output이 처음에 주어진 origin과 같아질 때 도전 횟수인 number에 1을 더해서 출력하였다. 

 

output과 origin이 같지 않을 경우, 즉 아직 origin으로 향하는 과정일 경우, output이 2로 나눠지면 2로 나눈 숫자를 output으로 넣었다. 

 

반면 2로 나눠지지 않는 숫자라면 else 문을 이용하여 끝에 붙은 '1'을 떼어냈다. 

 

그런데 위의 코드를 보면 중간에 elif문이 하나 더 있다. 

 

이 코드는 output이 origin으로 돌아갈 수 없는 경우를 걸러내기 위한 것이다.

• 맨 뒤의 1을 계속 떼어내다가 1이 붙어있지도 않고, 2로 나눠지지도 않는 output이 되었을 때
• 과정 중 origin을 만나지 못하고 output이 origin보다 작아졌을 때 

 

두 번째 예제(4, 42)가 '과정 중 origin이 되지 못하고 output이 origin보다 작아졌을 때' 의 경우이다. 

 

42 -> 21 -> 2 -> 1

 

과정 중 origin인 4가 되지 못하고 더 작은 수인 2로 간다. 이러한 경우를 걸러내기 위해 위 코드를 쓴다. 

 

또한 origin이 1일 때 '맨 뒤의 1을 계속 떼어내다가 1이 붙어있지도 않고 2로 나눠지지도 않는 output이 되었을 때'가 발생한다. 

 

origin=1 output=131 

 

131 -> 13 

 

이 경우에도 -1을 프린트한다. 이렇게 예외인 경우를 제외하여 코드를 짜서 문제를 해결하였다. 

 

 

♣ BFS(Breadth-First Search, 너비우선탐색)

나는 주어진 output으로부터 시작하여 origin으로 가면서 가능/불가능 여부를 판단하였는데 이 문제는 BFS라는 알고리즘으로 해결할 수 있는 문제였다. 그래서 BFS를 공부하기로 했다. 

 

너비우선탐색(BFS)은 그래프 탐색 중 하나이다. 그래프 탐색은 하나의 정점(노드)로부터 시작하여 차례대로 모든 노드들을 한 번씩 방문하는 것을 의미한다. 그래프 탐색은 크게 너비우선탐색(BFS)와 깊이우선탐색(DFS)로 나뉜다. 이 글에서는 너비우선탐색에 대해 알아본다. 

 

 

1. BFS와 DFS의 차이

 

BFS는 루트 노드(혹은 다른 임의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. 

즉 시작 정점(노드)로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 깊게 탐색하기와는 다르게 넓게 탐색하는 것이다. 

 

bfs 애니메이션

 

위의 애니메이션을 보면 맨 위의 1번 노드를 시작으로 해서 같은 너비의 노드부터 탐색한다. 깊이우선탐색(DFS)과 비교하면 차이점을 잘 알 수 있다. 

 

dfs 애니메이션

 

DFS를 보면 1번 노드를 시작으로 해서 해당 노드의 자식들을 모두 탐색한 후 다시 위로 올라가서 옆의 노드(형제 노드)로 이동한다는 것을 알 수 있다. 

 

 

2. BFS의 특징

- BFS는 출발노드에서 목표노드까지의 최단 경로를 구하는 데 유용하다. 출발노드로부터 가까운 노드부터 탐색하기 때문이다. DFS의 경우, 깊이를 끝까지 탐색한 후 옆으로 이동하기 때문에 최단 경로를 구하기 어렵다. 

- BFS를 구현할 때는 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 제대로 검사하지 않을 경우 무한루프에 빠질 수 있다. 

- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(queue)를 사용한다. 즉, 선입선출(FIFO) 원칙으로 노드들을 탐색한다. 아래는 큐를 이용한 BFS 과정을 보여준다. 

 

 

• (1)에서 루트노드(0)에 방문한다. 초기 큐에는 루트노드만 저장되어 있다. 
• (2), (3), (4), (5)에서 해당노드(0)와 인접하고, 방문된 적 없으며 큐에 저장되지 않은 노드를 큐에 저장한다. 
• (6)에서 가장 먼저 큐에 저장된 1번 노드로 이동해서 인접노드들의 조건을 확인한다. 이때 이동한 노드를 큐에서 뺀다. 인접한 노드가 아직 큐에 들어있지 않은 새로운 노드라면 큐에 저장한다. 

이 방식을 큐에 저장된 노드가 없을 때까지 반복한다. 

 

 

3. 백준 알고리즘 16953에 BFS 적용

 

문제 예제 그림을 보면 origin인 4에서 시작해서 2를 곱하거나 뒤에 1을 붙여가면서 숫자들이 늘어난다. 한 층 한 층 차례대로 숫자들이 늘어나므로 형제노드를 먼저 탐색하는 BFS 알고리즘을 적용하여 문제를 해결할 수 있을 것이다. 

 

♣ deque를 이용하여 BFS 방식으로(top-down) 해결하기

 

1. deque

deque는 스택과 큐의 기능을 모두 가진 자료구조로, 출입구를 양쪽에 가지고 있다. 오른쪽과 왼쪽 모두에서 요소를 입력, 출력 가능하다. 

 

2. 전체 코드

 

- queue = deque([(1, a)])

queue 안에 횟수와 origin을 넣는다. 횟수를 출력할 때 1을 더해야하므로 미리 1을 넣어둔다. 

 

queue 안에 요소가 존재하는 동안에 while문을 실행한다. queue 안의 요소들을 왼쪽부터 하나씩 값을 빼는데, 횟수는 cnt에, origin 수의 변화는 x에 대입한다. 

 

- if x==b

현재 숫자인 x가 목표 숫자인 b와 같으면 횟수를 출력하면서 while 문을 종료한다. 

 

- if x*2<=b / if x*10+1<=b

현재 숫자인 x가 b보다 작을 때는 x*2 와 x*10+1 을 수행하여 숫자를 바꾼다. 이때 바뀐 결과값이 b보다 크면 제외한다. 원하는 목표가 b이기 때문에 그보다 큰 값은 의미가 없기 때문이다. 

 

숫자 바꾸기를 수행했으니 cnt에 1을 더하고, 얻은 숫자를 묶어서 queue에 추가한다. 

예시 a=2 b=162에서 위의 코드를 실행하면  queue는 아래와 같이 변화한다. 

 

 

요소를 하나씩 빼면서 그에 *2나 *10+1을 수행하여 새로운 요소를 2개씩 늘려가는 것이다. 그러면 BFS에서 하는 것처럼 형제 노드부터 옮겨가면서 요소를 추가할 수 있다. 

 

queue가 비었는데도 cnt를 출력하지 못한 경우에는 -1을 출력한다. 

 

♣ 참고 자료

BFS

https://seokii.tistory.com/31

[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)이란?

 

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

DFS

https://velog.io/@rlwjd31/%ED%83%90%EC%83%89dfs-bfs

탐색 - DFS

https://star7sss.tistory.com/342

[탐색/BFS] 백준 16953 A → B - 파이썬(Python)