Open the Lock (BFS)

이번 문제 역시 LeetCode의 Stack, Queue 튜토리얼에 있는 'Open the Lock'이라는 문제다.

Explore - LeetCode

Queue를 활용해서 BFS 방식으로 푸는게 목적이기 때문에 지난번 Number of Islands처럼 DFS같은 방법은 사용하지 않고 진행했다. 이번 문제는 다음과 같다.

https://www.aliexpress.com/item/32848189629.html

• 0, 1, 2, 3, 4, 5, 6, 7, 8, 9가 적혀있는 슬롯 4개로 구성된 자물쇠가 있다.

• 사용자는 한번에 하나의 슬롯만 돌릴 수 있으며 슬롯은 회전 가능하다. 즉 0에서 9로, 9에서 0으로 슬롯을 돌릴 수 있다.

• 특정 비밀번호(deadend)에 도달할 경우 자물쇠는 잠기며 더이상 회전할 수 없다. 즉 이 비밀번호는 무조건 피해야 한다.

• 사용자가 0000에서 시작하여 목표 비밀번호(target)까지 맞추려면 슬롯을 몇 번이나 돌려야 하는가?

흔히 볼 수 있는 4자리 회전식 자물쇠를 브루트 포싱해서 몇번만에 목표 비밀번호에 도달할 수 있는가를 구하라는 문제다. 예를 들어 비밀번호가 0202일 때 0000부터 시작하기 때문에 0001, 0002, 0102, 0202 이렇게 4번 슬롯을 돌려야 비밀번호에 도달할 수 있다. 그러나 문제에서 주어지는 특정 비밀번호(deadend)에 도달하면 더이상 슬롯을 돌릴 수 없기 때문에 이 비밀번호들을 피해서 그리고 중복을 피해서 슬롯을 돌려야 한다. 그렇다면 이걸 어떻게 구할 수 있을까?

이전의 큐와 BFS로 생각해볼 때 한 슬롯씩 돌린 값을 큐에 집어넣어서 목표 비밀번호에 도달했는지 검사하는 방법을 사용해볼 수 있을 것이다. 시작 비밀번호는 0000이기 때문에 0001, 0010, 0100, 1000, 0009, 0090, 0900, 9000 처럼 한 슬롯씩 돌린 값을 큐에 집어넣은 후 다음 회차에서 각각의 비밀번호에 대해서도 한 슬롯씩 돌린 비밀번호를 큐에 집어넣으면서 반복하면 BFS 풀이법을 사용할 수 있다.

여기서 특이한 것은 큐에 들어있는 비밀번호에서 슬롯 회전을 통해 접근 가능한 모든 비밀번호들을 한꺼번에 큐에 삽입해야 한다는 것이다. 이게 무슨 말이냐면 맨 처음에는 시작 비밀번호가 0000이기 때문에 각 4자리 슬롯이 위, 아래로 회전된 0001, 0010, ..., 9000같은 비밀번호들을 큐에 집어넣을 수 있을 것이다. 그리고 다음 탐색에서 큐에 들어있는 비밀번호들(0001, 0010, ..., 9000)에서 접근 가능한 비밀번호들을 전부 한번에 큐에 삽입해야 한다는 것이다. 하나의 비밀번호에서 슬롯을 돌려서 접근할 수 있는 비밀번호는 8가지기 때문에 처음에는 0000의 8개, 그 다음에는 이 0000의 8개의 8개, 그 다음에는 8개의 8개의 8개처럼 각 탐색마다 점점 많은 비밀번호가 큐에 삽입될 것이다. 왜 이렇게 한번에 삽입해야 하는 것일까?

이는 탐색 대상 비밀번호를 맞추기까지 몇번이나 슬롯을 돌렸는지 정확하게 확인하기 위해서다. 첫번째 슬롯을 돌리든 두번째 슬롯을 돌리든 어쨌든 자물쇠의 슬롯을 돌려서 얻을 수 있는 비밀번호들을 큐에 저장한 이상 이 비밀번호들은 n번째 슬롯 회전으로 얻을 수 있는 비밀번호들이다. 이 비밀번호 중에서 찾고자 하는 비밀번호가 있다면 결과적으로 비밀번호는 0000부터 n번 슬롯을 회전해야 도달할 수 있다는 말이 된다. 그렇기 때문에 현재(n번째 탐색) 큐에 들어있는 모든 비밀번호에 대하여 접근 가능한 비밀번호들을 전부 얻어와서 다음 탐색(n+1번째 탐색)에서 삽입할 수 있도록 모두 큐에 삽입해야 하는 것이다. 이는 마치 슬롯을 하나 돌릴 때마다 자물쇠를 하나 더 만들어서 거기다가 새로 탐색을 시작한다고 생각할 수 있다.

그런데 순차적으로 접근할 수 밖에 없는 자료구조인 큐를 사용하는 이상 n번째 비밀번호(위의 그림에서는 0001)에서 접근 가능한 비밀번호들(위의 그림에서는 0002, 0011, ...)을 큐에 삽입하면 큐는 계속 늘어나게 된다. 그래서 어디까지가 원래 큐에 들어있던 비밀번호인지 확인할 필요가 있는데 많이 사용하는 방법으로는 탐색하기 전에 몇 개의 비밀번호가 들어있었는지 파악해서 반복문으로 그만큼만 꺼내서 접근 가능한 비밀번호들을 계산, 큐에 삽입하는 방법이 있다.

import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;


class Solution {
    public int openLock(String[] deadends, String target) {
        Queue<Integer> locksToTry = new LinkedList<Integer>();
        Set<Integer> triedLocks = new HashSet();
        Set<Integer> deadendLocks = new HashSet<Integer>();
        int targetLock = Integer.parseInt(target);
        
        for(String deadend: deadends){
            deadendLocks.add(Integer.parseInt(deadend));
        }
        
        int count = 0;
        locksToTry.add(0000);
        
        while(!locksToTry.isEmpty()){
            int currentTryingLocksCount = locksToTry.size();
            for(int index=0; index < currentTryingLocksCount; index++){
                int tryingLock = locksToTry.poll();
                if(deadendLocks.contains(tryingLock) || triedLocks.contains(tryingLock)){
                    continue;
                }
                if(tryingLock == targetLock){
                    return count;
                }
                
                int pos1 = tryingLock % 10;
                locksToTry.add((tryingLock - pos1) + (pos1 + 1) % 10);
                locksToTry.add((tryingLock - pos1) + (pos1 - 1 + 10) % 10);
                int pos2 = ((tryingLock - tryingLock % 10) / 10) % 10;
                locksToTry.add((tryingLock - pos2 * 10) + ((pos2 + 1) % 10) * 10);
                locksToTry.add((tryingLock - pos2 * 10) + ((pos2 - 1 + 10) % 10) * 10);
                int pos3 = ((tryingLock - tryingLock % 100) / 100) % 10;
                locksToTry.add((tryingLock - pos3 * 100) + ((pos3 + 1) % 10) * 100);
                locksToTry.add((tryingLock - pos3 * 100) + ((pos3 - 1 + 10) % 10) * 100);
                int pos4 = ((tryingLock - tryingLock % 1000) / 1000) % 10;
                locksToTry.add((tryingLock - pos4 * 1000) + ((pos4 + 1) % 10) * 1000);
                locksToTry.add((tryingLock - pos4 * 1000) + ((pos4 - 1 + 10) % 10) * 1000);
                
                triedLocks.add(tryingLock);        
            }
            count++;
        }
        
        return -1;
    }
}

이를 구현한 로직은 위와 같다. 먼저 이미 탐색한 자물쇠 번호는 다시 탐색하지 않도록 따로 HashSet으로 만들어 두고 문자열로 주어진 deadend 비밀번호들도 비교하기 편하도록 정수로 변환시켰다. 그리고 탐색을 시작할 큐에 시작 비밀번호인 0000를 삽입하고 탐색을 시작한다.

 

이후 큐가 비어있지 않는 동안 탐색을 시작하는데 만약 큐가 빌 때까지 못 찾았다면 해당 비밀번호에 접근할 수 있는 방법이 없는 것이기 때문에 문제 조건에 따라 -1을 반환한다. 반복문 내부에서는 현재 큐에 들어있는 요소들의 갯수, 즉 n-1번째 탐색에서 접근할 수 있었던 비밀번호들의 갯수를 파악해서 그만큼만 반복문을 돌아서 비밀번호를 얻어와서 탐색한다. 위에서 언급했듯이 n번째 탐색에서 새로 큐에 삽입하는 비밀번호들과 헷갈리지 않도록 하기 위해서다.

 

이때 각 비밀번호마다 deadend 비밀번호는 아닌지 이미 탐색한 비밀번호는 아닌지 확인한다. 만약 찾고있는 비밀번호와 현재 비밀번호가 동일하다면 바로 count 변수를 return하여 슬롯을 돌린 횟수를 반환한다. 그렇지 않다면 한자리씩 슬롯을 돌린 비밀번호들을 큐에 삽입하고 원래 비밀번호를 이미 탐색한 비밀번호에 삽입하여 나중에 다시 탐색하지 않도록 한다. 이 과정을 반복문 내에서 모든 비밀번호에 적용한 후 반복문이 끝나면 해당 회차의 탐색을 마친 것이기 때문에 슬롯을 돌린 횟수(count)를 추가한다.

이렇게 하면 마치 Tree 자료형처럼 슬롯을 돌린 비밀번호를 한 계층씩 뿌리내려가면서 비밀번호를 찾을 때까지 슬롯을 돌린 횟수를 구할 수 있다. 트리의 계층을 구하는 것과 비슷하다고 할 수 있을 것이다.

 

 

재밌던 것은 구현 과정에서 착오가 있어서 이미 탐색한 자물쇠 번호를 저장하는 자료구조를 Set이 아닌 ArrayList로 구현했더니 문제는 풀리는데 성능이 정말 낮게 나왔다.

좌측이 ArrayList, 우측이 HashSet.

그래서 뭐가 문제인가 생각해보다가 이미 탐색한 비밀번호를 저장하는데 어차피 중복을 허용할 이유도 없기 때문에 Set 자료구조를 사용할 수 있지 않을까? 해서 HashSet으로 적용했더니 오른쪽처럼 속도는 30분의 1로, 메모리 사용량은 절반으로 줄어든 것을 볼 수 있었다. 자료구조의 특성을 잘 알고 활용하는 것의 중요성을 알 수 있던 경험이었다.

 

 

이번 문제는 중간까지는 혼자 해보다가 카운트를 구하는 방법이 떠오르지 않아 풀이를 보고 이해했다. 예전에 다른 글에서 혼자 문제를 풀다가 한두시간정도 해보고 안되면 풀이를 보는게 더 효율적이라는 말을 들어서 나도 그렇게 해보고 있다. 꼭 붙잡고 있는다고 풀리는 것도 아니고 시간도 무한정 있는게 아니니...