[leetcode] Open the Lock

문제

• 문제 링크
• 네개의 원형 바퀴 형태를 가진 자물쇠가 있다. 각 바퀴는 0~9의 값을 갖고, 바퀴를 돌려서 슬롯에 값을 맞출 수 있다. 자물쇠는 "0000"으로 세팅되어 있다. 그리고 문자열 배열인 deadends와 문자열 target이 주어진다. deadends에는 특정 자물쇠 값들이 들어있는데, 자물쇠가 deadends에 있는 값과 같아지면 자물쇠는 열 수 없게 된다. target은 자물쇠를 열 수 있는 값이다. deadends에 막히지 않고 target에 도달하기 위해 자물쇠 바퀴를 돌릴 때, 가장 짧은 횟수를 구해야 한다. 만약 도달할 수 없다면 -1을 반환한다.
• 제약 조건
  • deadends 길이: 1 <= deadends.length <= 500
  • target은 deadends에 포함되지 않는다.

풀이

풀기 전

• target에 도달하기 위한 필승법이 있을까 했는데 딱히 없는 거 같았다. 자물쇠의 경우의 수를 계산했을 때 10^4로 그리 크지 않아서 모든 경우의 수를 체크할 수 있겠다 싶었다.
• 경우의 수가 작아서 DFS로 돌려도 되지만, 최단 거리를 구하는 문제이기 때문에 BFS를 사용하면 런타임 시간을 조금은 줄일 수 있을 거 같다.

코드

class Solution {
    private int BFS(Set<String> dead, String target) {
        Queue<StringBuilder> q = new LinkedList<>();
        q.add(new StringBuilder("0000"));  // 시작점을 큐에 넣는다.

        int depth = 0;
        while (!q.isEmpty()) {
            int size = q.size();

            for (int i=0; i<size; i++) {
                StringBuilder now = q.poll();
                
                for (int k=0; k<4; k++) {
                    StringBuilder[] next = new StringBuilder[2];
                    
                    // 자물쇠는 두 방향으로 돌릴 수 있으므로 두 경우 모두 고려해준다.
                    next[0] = new StringBuilder(now);
                    next[1] = new StringBuilder(now);
                    next[0].setCharAt(k, (char) ((now.charAt(k) - '0' + 1) % 10 + '0'));
                    next[1].setCharAt(k, (char) ((now.charAt(k) - '0' + 9) % 10 + '0'));

                    for (StringBuilder sb : next) {
                    	// 도달하면 안 되는 문자열에 있는지 체크한다.
                        if (dead.contains(sb.toString()))
                            continue;

						// 만약 목적지에 도착하면 종료한다.
                        if (target.equals(sb.toString()))
                            return depth + 1;
                            
                        q.add(sb);
                        dead.add(sb.toString());  // dead를 visit 용도로도 사용한다.
                    }
                }
            }
            depth++;
        }
        return -1;
    }

    public int openLock(String[] deadends, String target) {        		
    	// edge case
        if (target.equals("0000"))
            return 0;

		// deadends가 배열이기 때문에 탐색이 빠른 set으로 바꿔준다.
        Set<String> dead = new HashSet<>();
        for (String s : deadends) {
            dead.add(s);
        }

		// edge case
        if (dead.contains("0000"))
            return -1;

		// BFS 탐색 시작
        return BFS(dead, target);
    }
}

푼 후

• 풀이를 생각하는 건 어렵지 않았는데, 문자열 다루는 게 까다로웠다. 문자열을 정수형으로 바꿨다가 StringBuilder로 썼다가 그랬다. 정수형의 경우엔 문자열에서 왔다갔다 하는 게 오히려 느릴 거 같았고, 문자열을 그대로 사용하기에도 느려서 StringBuilder를 사용했다.
• 자물쇠 바퀴 하나에서 가능한 숫자 개수를 n이라고 하면 시간 복잡도는 O(n^4)이다. set에는 최대 자물쇠에서 가능한 수만큼 들어갈 수 있기 때문에 공간 복잡도도 O(n^4)이다.