hyelie
hyelie
Hyeil Jeong
       
글쓰기    관리    수식입력
  • 전체보기 (495)
    • PS (283)
      • Algorithm (28)
      • PS Log (244)
      • Contest (6)
      • Tips (5)
    • Development (52)
      • Java (14)
      • Spring (23)
      • SQL (2)
      • Node.js (2)
      • Socket.io (3)
      • Study (4)
      • Utils (4)
    • DevOps (36)
      • Git (5)
      • Docker (4)
      • Kubernetes (2)
      • GCP (3)
      • Environment Set Up (8)
      • Tutorial (12)
      • Figma (2)
    • CS (74)
      • OOP (7)
      • OS (24)
      • DB (2)
      • Network (24)
      • Architecture (0)
      • Security (2)
      • Software Design (0)
      • Parallel Computing (15)
    • Project (15)
      • Project N2T (5)
      • Project ASG (0)
      • Project Meerkat (1)
      • Model Checking (7)
      • Ideas (2)
    • 내가 하고싶은 것! (34)
      • Plan (16)
      • Software Maestro (10)
      • 취준 (8)
hELLO · Designed By 정상우.
hyelie
PS/Algorithm

2020/07/04 공부 - backtracking

PS/Algorithm

2020/07/04 공부 - backtracking

 오늘은 저번에 이어 backtrack의 다른 예제를 풀었다. 백준 2580번 스도쿠이다. 내가 알고 있는 CSP와 굉장히 유사한 문제이기 때문에 backtrack으로 푸는 것이 좋다. 숫자를 채워 넣을 때 lookahead 등의 heuristics를 쓸 수도 있지만 귀찮아서 순서대로 채워 넣었다.

 먼저 backtrack의 pseudo code는 다음과 같았다. 이 pseudo code를 따라가면 코드를 완성할 수 있다.

 

DFS(list, depth, N) {
if (depth == N) return;
else {
if (bounding_function() == true)
DFS(list, depth + 1, N)
else
return;
}
}
DFS(list, 0, N)

 

 스도쿠에서 boundnig function은 다음과 같이, 가로줄/세로줄/3by3 그룹에서 모든 숫자를 2번 이상 사용했으면 안 된다.(문제에서 주어져 있으므로 세부 설명은 생략) C++을 오랜만에 만져봐서 배열을 초기화하는 데 자꾸 컴파일 에러가 걸려서 애먹었다. 코드가 좀 난잡하긴 하지만 하나하나 확실하게 하는 것에 초점을 두었다.

 

// 어떤 새로운 row, col에 숫자 n을 집어넣었을 때 스도쿠 규칙을 안 깨는지 검사해주는 함수. 깨면 false, 안깨면 true return.
bool sudoku_possible(vector<vector<int>>& board, int row, int col, int n) {
int one_to_nine_arr[10] = {};
// 세로줄 검사
for (int i = 1; i <= 9; i++) {
one_to_nine_arr[board[i-1][col]]++;
}
one_to_nine_arr[n]++;
for (int i = 1; i <= 9; i++) {
if (one_to_nine_arr[i] >= 2) return false;
}
// 가로줄 검사
for (int i = 1; i <= 9; i++) one_to_nine_arr[i] = 0;
for (int i = 1; i <= 9; i++) {
one_to_nine_arr[board[row][i-1]]++;
}
one_to_nine_arr[n]++;
for (int i = 1; i <= 9; i++) {
if (one_to_nine_arr[i] >= 2) return false;
}
// 3 by 3 그룹 검사
for (int i = 1; i <= 9; i++) one_to_nine_arr[i] = 0;
int row_group = row / 3;
int col_group = col / 3;
for (int i = 3*row_group; i < 3 * row_group + 3; i++) {
for (int j = 3 * col_group; j < 3 * col_group + 3; j++) {
one_to_nine_arr[board[i][j]]++;
}
}
one_to_nine_arr[n]++;
for (int i = 1; i <= 9; i++) {
if (one_to_nine_arr[i] >= 2) return false;
}
return true;
}


 다음으로 DFS 부분이다. 기존에 비어 있던 칸들(0으로 입력되어 있는 부분)을 blank라는 pair vector로 입력받았고 blank의 size가 DFS에서 목표로 하는 depth가 될 것이다. 이 값을 blank_num으로 했고 각 depth에서 blank[depth]를 탐색하게 만들었다.

 DFS를 void로 선언했기 때문에 complete라는 새로운 변수를 하나 넣어서 이게 true이면 종료 조건을 달성하게 만들었다.

 bounding funtion 부분은 blank[depth]에 1부터 9까지 수를 넣었을 때, 만족하면 다음 DFS를 진행하고, 만약 이 DFS 결과 complete가 참이라면 바로 return하게 만들었다. 만약 불가능하다면 다음 수를 탐색하게 만들었고, 이 때 1부터 9까지 모든 수가 불가능하다면 채워넣은 칸을 0으로 다시 초기화한 뒤 return했다.
​

void DFS(vector<vector<int>>& board, vector<pair<int, int>>& blank, int depth, int blank_num, bool& complete) {
if (depth == blank_num || complete == true) {
complete = true;
return;
}
else {
bool ispossible = false;
for (int i = 1; i <= 9; i++) {
if (sudoku_possible(board, blank[depth].first, blank[depth].second, i)) {
board[blank[depth].first][blank[depth].second] = i;
DFS(board, blank, depth + 1, blank_num, complete);
if (complete == true) return;
continue;
}
}
board[blank[depth].first][blank[depth].second] = 0;
return;
}
}


 전체적인 코드의 구조는 pseudo code와 동일하게 만들었다. 아래 코드는 입/출력 부분이다.

void solve() {
int blank_num = 0; // 채워야 하는 것들 개수
vector<vector<int>> board(9, vector<int>(9)); // 스도쿠 판
vector<pair<int, int>> blank; // 빈 칸 list
bool complete = false;
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
int input;
cin >> input;
board[row][col] = input;
if (input == 0) {
blank.push_back({ row, col });
blank_num++;
}
}
}
DFS(board, blank, 0, blank_num, complete);
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
cout << board[row][col]<<' ';
}
cout << '\n';
}
}

 

 

 다음, 14888번을 풀었다. 이 문제는 search 과정에서 bounding function을 사용하지 않고 leaf node에서 bounding function을 사용하기 때문에 backtrack이라기보다는 재귀를 이용한 DFS라는 주제가 조금 더 맞는 것 같은데, 일단 backtrack 주제에 포함되어 있어서 여기서 풀었다.

 연산자 4종류를 나열할 수 있는 수는, (N-1)! / [(+)!(-)!(*)!(/)!] 일 것이다. 여기서 N = 12이므로 11!은 약 300백만이고, 컴퓨터가 1초에 약 10억개의 연산을 할 수 있으니 연산량은 충분하므로 완전 탐색으로 진행해도 된다.

 고등학교 과정에서 배우는 수의 나열을 위해 DFS를 진행한다. 이 문제는 brute-force에 좀 더 가깝기 때문에 backtrack에서 사용하기 위한 bounding function은 없다.

 DFS는 다음과 같다. 이렇게 진행하면 각 연산자의 숫자가 0이 될 때까지 모든 경우의 수를 알아서 계산해 준다. 앞과 같이 depth와 최대 depth의 크기를 받아서 depth가 N-1과 같아지면 그만하고 return. 아니라면 탐색을 계속 진행한다.

 

void DFS(vector<int>& arr, int num_plus, int num_minus, int num_mul, int num_div, int depth, int N, int cal_result, int& max_num, int& min_num) {
if (depth == N-1) {
max_num = max(cal_result, max_num);
min_num = min(cal_result, min_num);
}
else {
if (num_plus > 0) {
DFS(arr, num_plus - 1, num_minus, num_mul, num_div, depth + 1, N, cal_result + arr[depth + 1], max_num, min_num);
}
if (num_minus > 0) {
DFS(arr, num_plus, num_minus - 1, num_mul, num_div, depth + 1, N, cal_result - arr[depth + 1], max_num, min_num);
}
if (num_mul > 0) {
DFS(arr, num_plus, num_minus, num_mul - 1, num_div, depth + 1, N, cal_result * arr[depth + 1], max_num, min_num);
}
if (num_div > 0) {
DFS(arr, num_plus, num_minus, num_mul, num_div - 1, depth + 1, N, cal_result / arr[depth + 1], max_num, min_num);
}
}
}

 

입력부는 다음과 같다.

void solve() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
vector<int> simple_operator(4);
for (int i = 0; i < 4; i++) {
cin >> simple_operator[i];
}
int max_num = -1000000001;
int min_num = +1000000001;
DFS(arr, simple_operator[0], simple_operator[1], simple_operator[2], simple_operator[3], 0, arr.size(), arr[0], max_num, min_num);
cout << max_num << '\n' << min_num;
}

'PS > Algorithm' 카테고리의 다른 글

2020/07/08 공부 - dynamic programming  (0) 2022.06.21
2020/07/07 공부 - dynamic programming  (0) 2022.06.21
2020/07/06 공부 - dynamic programming  (0) 2022.06.21
2020/07/06 공부 - backtracking  (0) 2022.06.21
2020/07/02 공부 - backtracking  (0) 2022.06.21
    hyelie
    hyelie

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.