이 문제에서는 숫자 n이 주어졌을 때, 모바일 키패드 버튼을 눌러서 만들 수 있는 모든 n자리 숫자 패턴을 출력해야 합니다. 단, 버튼을 누를 때는 현재 누른 버튼에 인접한 버튼만 누를 수 있다는 제약 조건이 있습니다. 즉, 왼쪽, 오른쪽, 위, 아래 방향에 위치한 키만 연속해서 누를 수 있습니다.
기존 모바일 키패드의 구조
구형 휴대폰의 키패드는 다음과 같은 배치를 하고 있습니다.
| 1 | 2 ABC | 3 DEF |
| 4 GHI | 5 JKL | 6 MNO |
| 7 PQRS | 8 TUV | 9 WXYZ |
| * | 0 | # |
여기서 '*'와 '#' 키는 유효한 숫자가 아니므로 탐색 대상에서 제외됩니다.
문제 이해를 위한 예시
n = 2인 경우, 두 자리 숫자 패턴을 생성하는 과정을 살펴보겠습니다.
입력: n=2 출력: 12 14 21 23 25 32 36 41 45 47 52 54 56 58 63 65 69 74 78 85 87 89 80 96 98
예를 들어 '1'에서 시작한다면, '1'의 인접 키는 '2'(오른쪽)와 '4'(아래)뿐이므로 '12'와 '14'라는 두 가지 패턴만 만들 수 있습니다.
해결 접근 방식: 깊이 우선 탐색(DFS)
이 문제는 깊이 우선 탐색(Depth-First Search, DFS)을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 흐름은 다음과 같습니다.
1. 키패드의 모든 유효한 키를 하나씩 선택하여 숫자의 첫 번째 자릿수로 지정합니다.
2. 현재 위치에서 왼쪽, 오른쪽, 위, 아래 방향으로 이동 가능한 키를 재귀적으로 탐색(DFS)하여 나머지 자릿수를 채웁니다.
3. 패턴의 길이가 n에 도달하면 해당 패턴을 출력하고 백트래킹으로 되돌아갑니다.
구현 코드
위 알고리즘을 C++로 구현한 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
bool isSafe(int x, int y, bool Visited[][3]) {
return (x >= 0 && x < 4 && y >= 0 && y < 3 && !Visited[x][y]);
}
void searchNumber(bool visited[][3], int Keypad[][3], int n, string pattern, int x, int y) {
pattern.push_back((Keypad[x][y] + '0'));
if (pattern.size() == n) {
cout<<pattern<<"\t";
return;
}
static int row[] = { 0, 1, 0, -1 };
static int col[] = { 1, 0, -1, 0 };
visited[x][y] = true;
for (int k = 0; k < 4; k++)
if (isSafe(x + row[k], y + col[k], visited) && Keypad[x + row[k]][y + col[k]] != -1)
searchNumber(visited, Keypad, n, pattern, x + row[k], y + col[k]);
visited[x][y] = false;
pattern.pop_back();
}
void GenerateNDigitNumber(int Keypad[][3], int n) {
bool visited[4][3];
memset(visited, false, sizeof(visited));
for (int i = 0; i < 4; i++)
for (int j = 0; j < 3; j++)
if (Keypad[i][j] != -1)
searchNumber(visited, Keypad, n, "", i, j);
}
int main() {
int Keypad[4][3] ={
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 },
{ -1, 0, -1 }
};
int n = 2;
cout<<"All "<<n<<" digit number generated from keypad are :\n";
GenerateNDigitNumber(Keypad, n);
return 0;
}코드 설명
isSafe 함수: 다음에 이동할 좌표가 키패드 범위 내에 있고, 아직 방문하지 않은 위치인지 검사합니다.
searchNumber 함수: 핵심 재귀 함수입니다. 현재 키를 패턴에 추가한 뒤, 패턴 길이가 n이면 출력합니다. 그렇지 않으면 상하좌우 네 방향을 확인하며 유효한 키(-1이 아닌 값)에 대해 재귀 호출을 수행합니다. 탐색이 끝나면 방문 표시와 패턴을 원복하는 백트래킹 처리를 통해 다른 경로도 탐색할 수 있게 합니다.
GenerateNDigitNumber 함수: 키패드 배열에서 유효한 숫자 키(값이 -1이 아닌 위치)를 모두 찾아 각각을 시작점으로 searchNumber를 호출합니다. '*'와 '#'에 해당하는 위치는 -1로 초기화되어 자동으로 제외됩니다.
실행 결과
All 2 digit number generated from keypad are − 12 14 23 25 21 36 32 45 47 41 56 58 54 52 69 65 63 78 74 89 80 87 85 98 96 08
출력 결과를 보면 각 숫자 쌍이 키패드상에서 반드시 상하좌우로 인접해 있는 것을 확인할 수 있습니다. 예를 들어 '13'은 '1'과 '3'이 인접하지 않으므로 결과에 포함되지 않습니다.
마무리
이처럼 DFS와 백트래킹을 결합하면 키패드 기반의 조합 문제를 체계적으로 해결할 수 있습니다. 시간 복잡도는 가능한 경로의 수에 비례하며, n이 커질수록 생성되는 패턴의 개수는 지수적으로 증가하므로 n의 크기에 유의해야 합니다.