안드로이드 스마트폰에서 흔히 볼 수 있는 3x3 패턴 잠금 화면을 생각해 봅시다. 두 정수 m과 n이 주어지며(1 ≤ m ≤ n ≤ 9), 이때 최소 m개의 키부터 최대 n개의 키까지 사용하여 만들 수 있는 잠금 해제 패턴의 총 개수를 구하는 것이 목표입니다.
문제의 규칙
패턴을 만들 때 반드시 지켜야 할 규칙은 다음과 같습니다.
- 각 패턴은 최소 m개, 최대 n개의 키를 연결해야 합니다.
- 모든 키는 중복 없이 한 번씩만 사용할 수 있습니다.
- 패턴에서 연속된 두 키를 잇는 선분이 다른 키를 통과한다면, 그 키는 반드시 미리 선택되어 있어야 합니다. 즉, 아직 선택되지 않은 키를 뛰어넘는 것은 허용되지 않습니다.
- 키를 누르는 순서도 하나의 패턴에 포함되므로 순서가 중요합니다.
예를 들어 입력이 m = 1, n = 1이라면, 키를 하나만 사용하는 패턴의 개수를 구하는 것이므로 출력은 9가 됩니다.
접근 방법: 깊이 우선 탐색(DFS)
이 문제는 백트래킹 기반의 깊이 우선 탐색(DFS)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 10 x 10 크기의
skip배열을 정의합니다. 이 배열은 두 키 사이를 직선으로 이동할 때 '건너뛰게 되는' 키의 번호를 저장합니다. 예를 들어 1에서 3으로 이동하려면 2를 거쳐야 하므로skip[1][3] = 2입니다. dfs(node, len, visited)함수를 정의합니다. 현재 노드에서 시작하여 남은 길이가 len일 때 만들 수 있는 패턴의 개수를 반환합니다.- len이 0이면 유효한 패턴 하나를 완성한 것이므로 1을 반환합니다.
- 현재 노드를 방문 처리한 후, 방문하지 않은 인접 키 중에서 건너뛰어야 하는 키가 이미 방문되었거나 건너뛸 키가 없는 경우에만 재귀 호출을 진행합니다.
- 탐색이 끝나면 방문 여부를 되돌려(백트래킹) 다른 경로 탐색이 가능하도록 합니다.
대칭성 활용하기
주목할 점은 9개의 키가 가지는 대칭성입니다. 모서리에 있는 키 1, 3, 7, 9는 서로 대칭 관계에 있으므로 결과가 동일하고, 변의 중앙에 있는 키 2, 4, 6, 8 역시 마찬가지입니다. 따라서 각 그룹에서 대표 키 하나(1과 2)만 탐색한 뒤 4를 곱하고, 중앙 키 5는 별도로 탐색하면 전체 경우를 빠짐없이 계산할 수 있습니다.
C++ 구현 코드
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int skip[10][10];
int dfs(int node, int len, vector<bool>& visited){
if (len == 0)
return 1;
visited[node] = true;
int ret = 0;
for (int i = 1; i <= 9; i++) {
if (!visited[i] && (skip[node][i] == 0 || visited[skip[node][i]])) {
ret += dfs(i, len - 1, visited);
}
}
visited[node] = false;
return ret;
}
int numberOfPatterns(int m, int n){
memset(skip, 0, sizeof(skip));
skip[1][3] = skip[3][1] = 2;
skip[1][7] = skip[7][1] = 4;
skip[3][9] = skip[9][3] = 6;
skip[7][9] = skip[9][7] = 8;
skip[4][6] = skip[6][4] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[1][9] = skip[9][1] = 5;
vector<bool> visited(10);
int ret = 0;
for (int i = m; i <= n; i++) {
ret += (dfs(1, i - 1, visited) * 4);
ret += (dfs(2, i - 1, visited) * 4);
ret += dfs(5, i - 1, visited);
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.numberOfPatterns(1,1));
}
실행 결과 확인
입력
1, 1
출력
9
정리
이 문제는 상태 공간이 제한적(최대 9개의 키)이므로 완전 탐색인 DFS로 충분히 해결할 수 있습니다. skip 배열로 '건너뛰기 규칙'을 명확하게 모델링하고, 키 배치의 대칭성을 활용하면 탐색 시간을 약 9배 가까이 줄일 수 있다는 점이 핵심입니다. 실제 안드로이드 잠금 화면의 보안 정책이 어떻게 알고리즘으로 구현되는지 이해하는 좋은 예제이기도 합니다.