파사드(Facade) 패턴
현대의 소프트웨어는 수많은 클래스, 메서드, 라이브러리, API 등으로 이루어져있다.
클라이언트가 모든 세부사항을 직접 알고 접근하는 건 복잡하고, 유지보수가 어려워질 수 있다.
그래서 이런 세부 사항을 한곳에서 담당하여 기능을 정의해두고 사용자는 간단하게 사용하는 패턴이다
-
Facade (파사드)
클라이언트가 직접 사용하게 되는 단순한 인터페이스를 제공한다.
클라이언트의 요청을 받아 적절한 서브시스템으로 전달하고 처리한다. -
Subsystem Classes (서브시스템 클래스)
실제로 기능을 수행하는 여러 클래스로, 파사드가 이들을 내부적으로 호출하여 작업을 처리한다. -
Client (클라이언트)
파사드 인터페이스를 통해 서브시스템의 기능을 사용한다.
어째 말만 들으면 '그냥 평소에 하던거 아닌가? GameManager 같은 Manager 같은걸로 하는거잖아'라고 할 수 있다.
근데 맞다. 이미 그런 식으로 모아서 제작하고 실제 사용은 간단하게 정리를 해두는 것이 파사드 패턴인거다.
백트래킹(Backtracking)
백트래킹은 해를 찾아가는 도중에 ‘이 길은 아니다’가 확정되면, 즉시 되돌아(Backtrack) 가서 다른 경로를 탐색하는 알고리즘 설계 기법이다.
브루트포스와 유사하지만, 가능성이 없는 곳은 빠르게 걸러서 시간을 아끼는 방식이다.
이와 같이 거르는 것을 가지치기(Pruning)라고 한다.
방식에 따라 DFS, BFS로 나뉜다.
DFS는 깊이 우선 탐색이고
BFS는 너비 우선 탐색이다.
N-Queen 문제
백트래킹의 대표적 문제 중 하나로, 체스의 퀸을 N x N 체스판에 N개 배치했을 때 서로를 공격할 수 없는 위치에 놓을수 있는 방법이 있는지 찾는 문제이다.
퀸은 대각선, 수직, 수평을 전부 이동할 수 있으며, 이 퀸들을 서로 공격할 수 없는 위치에 배치하는게 이번 문제의 해다.
Q를 퀸, ■을 남은 칸으로 표현했을 때
Q ■ ■ ■
■ ■ Q ■
■ ■ ■ ■
■ ■ ■ ■
여기까지 배치하면 다음 Q을 배치할 수 없다는 사실을 알 수 있다.
그렇게 되면 이전 단계로 돌아가 다시 배치를 한다.
Q ■ ■ ■
■ ■ ■ Q
■ Q ■ ■
■ ■ ■ ■
여기까지 와도 4번째 줄에 배치할 수 없으니 다시 돌아간다.
■ Q ■ ■
■ ■ ■ Q
Q ■ ■ ■
■ ■ Q ■
최종적으로 이렇게 배치했을 때 조건에 맞게 배치되며 종료되게 된다.
#include <iostream>
#include <vector>
using namespace std;
// 체스판 출력 함수
void printBoard(const vector<vector<int>>& board, int n)
{
cout << "====" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 1) {
cout << "Q ";
}
else {
cout << ". ";
}
}
cout << endl;
}
cout << "====" << endl;
}
// 해당 위치가 유망한지 확인하는 함수
bool isPromising(const vector<vector<int>>& board, int row, int col, int n)
{
// 같은 행은 퀸을 배치하지 않으므로 검사하지 않음
// 같은 열에 퀸이 있는지 확인
for (int i = 0; i < row; i++)
if (board[i][col] == 1)
return false;
// 왼쪽 대각선에 퀸이 있는지 확인
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
// 오른쪽 대각선에 퀸이 있는지 확인
for (int i = row, j = col; i >= 0 && j < n; i--, j++)
if (board[i][j] == 1)
return false;
// 모든 검사를 통과했으므로 유망함
return true;
}
// 백트래킹을 사용하여 N-Queen 문제 해결
void solveNQueens(vector<vector<int>>& board, int row, int n)
{
// 모든 행에 퀸을 배치했으면 해결책 출력
if (row == n)
{
printBoard(board, n);
return;
}
// 현재 행의 각 열에 퀸 배치 시도
// 4x4 체스판이면 0, 1, 2, 3 열을 차례로 시도
for (int col = 0; col < n; col++)
{
// 해당 위치(row, col)가 유망한지 확인!
if (isPromising(board, row, col, n))
{
// 퀸 배치
board[row][col] = 1;
// 다음 행으로 재귀 호출
solveNQueens(board, row + 1, n);
// 백트래킹: 현재 위치의 퀸을 제거
board[row][col] = 0;
}
// 유망하지 않으면 퀸을 배치하지 않고 다음 열로 넘어가는 구조
}
}
int main()
{
int n = 4; // 4-Queen 문제
vector<vector<int>> board(n, vector<int>(n, 0)); // 4 x 4 체스판 초기화
solveNQueens(board, 0, n);
}