351. Android Unlock Pattern

https://leetcode.com/problems/android-unlock-patterns/

Account Login - LeetCode

 

 unlock pattern하는 문제.  2차원 배열에서 방향을 줄때 상대적인 위치값을 주는게 익숙했는데 3x3로 고정되어있어서 방문했는지, 2칸 점프할 수 있는지 여부를 좀 더 효율적인 방법으로 확인 가능하다.

 

 상대적인 위치값: {0, 1}, {1, 0}로 더하주면 각각 right로 1칸, bottom으로 한 칸 이동이다.  

 

class Solution {
public:
    int fromTo[10][10];
    
    int visited[10];
    
    int traverse(int cur, int m, int n, int d){
        int ret = 0;
        
        if(n < d){
            return 0;
        }
        
        visited[cur] = 1;
        
        if(m <= d){
            ret += 1;
        }
        
        for(int i = 1; i < 10; i++){
            if(!visited[i] && visited[fromTo[cur][i]]){
                ret += traverse(i, m, n, d + 1);
            }
        }
        
        visited[cur] = 0;
        return ret;
    }
    
    int numberOfPatterns(int m, int n) {
        int ans = 0;
        
        visited[0] = 1;
        
        fromTo[1][3] = fromTo[3][1] = 2;
        fromTo[1][7] = fromTo[7][1] = 4;
        fromTo[3][9] = fromTo[9][3] = 6;
        fromTo[7][9] = fromTo[9][7] = 8;
        
        fromTo[1][9] = fromTo[9][1] = fromTo[3][7] = fromTo[7][3] = fromTo[2][8] = fromTo[8][2] 
            = fromTo[4][6] = fromTo[6][4] = 5;
        
        ans += traverse(1, m, n, 1) * 4;
        ans += traverse(2, m, n, 1) * 4;
        ans += traverse(5, m, n, 1);
        return ans;
    }
};

 문제에서 from 1 to 3로 점프할 때 2번이 방문되어야 하는 조건이 있으므로, fromTo 배열의 [1][3] 값에 2를 저장하면 traverse 시에 visited 배열로 2번이 방문했는지 안했는지 효율적으로 판단할 수 있다.

 

Time complexity: O(N^2), 방문한 노드를 제외한 모든 노드로 갈 수 있다고 가정할 때 N*(N + 1) / 2

Space complexity: O(N^2)

 

N == 9