[C++] 백 트래킹(Back Tracking)

백 트래킹(Back Tracking)

한정 조건이 주어졌을 때 해를 얻을 때까지 모든 경우의 수를 검사하는 알고리즘으로 가다가 다시 돌아와서 다른 길로 간다.

모든 경우를 고려해야 하므로 재귀 함수를 이용한 DFS를 사용한다.

기본 원리

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

#include <iostream>
using namespace std;

int n, m;
int number[8]; 
bool ck[9];

// 중복 없이 M개를 고른 수열
void DFS(int t)
{
	if (t == m) {
		for (int i = 0; i < m; i++)
			cout << number[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (!ck[i]) {
			ck[i] = true;
			number[t] = i;
			DFS(t + 1);
			ck[i] = false;
		}
	}
}

int main() 
{
	cin >> n >> m;
	DFS(0);
}

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

www.acmicpc.net

#include <iostream>
using namespace std;

int n, m;
int number[8];

// 중복 없이 M개를 고른 오름차순 수열
void DFS(int t, int cnt)
{
	if (t == m) {
		for (int i = 0; i < m; i++)
			cout << number[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = cnt; i <= n; i++) {
		number[t] = i;
		DFS(t + 1, i + 1);
	}
}

int main()
{
	cin >> n >> m;
	DFS(0, 1);
}

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

www.acmicpc.net

#include <iostream>
using namespace std;

int n, m;
int number[8];

// 중복 허용하고 M개를 고른 수열
void DFS(int t)
{
	if (t == m) {
		for (int i = 0; i < m; i++)
			cout << number[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; i++) {
		number[t] = i;
		DFS(t + 1);
	}
}

int main() 
{
	cin >> n >> m;
	DFS(0);
}

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

www.acmicpc.net

#include <iostream>
using namespace std;

int n, m;
int number[8];

// 중복 허용하고 M개를 고른 비내림차순 수열
// 비내림차순 수열: 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하는 수열
void DFS(int t, int cnt)
{
	if (t == m)	{
		for (int i = 0; i < m; i++)
			cout << number[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = cnt; i <= n; i++)	{
		number[t] = i;
		DFS(t + 1, i);
	}
}

int main() 
{
	cin >> n >> m;
	DFS(0, 1);
}

문제

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

#include <iostream>
using namespace std;

int answer = 1e9;
int N, arr[20][20], start[10];

void dfs(int index, int count)
{
	if (index == N / 2) {
		int link[10]{};
		for (int i = 0, index1 = 0, index2 = 0; i < N; ++i)
			start[index1] == i ? index1++ : link[index2++] = i;

		int t1 = 0, t2 = 0;
		for (int i = 0; i < N / 2; ++i)
			for (int j = i + 1; j < N / 2; ++j) {
				t1 += arr[start[i]][start[j]] + arr[start[j]][start[i]];
				t2 += arr[link[i]][link[j]] + arr[link[j]][link[i]];
			}

		if (abs(t1 - t2) < answer)
			answer = abs(t1 - t2);
		return;
	}

	for (int i = count; i < N; ++i) {
		start[index] = i;
		dfs(index + 1, i + 1);
	}
}

int main()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> arr[i][j];

	dfs(0, 0);
	cout << answer;
}

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

#include <iostream>
#include <algorithm>
using namespace std;

int answer, N, S;
int num[20], subsequence[20];

void dfs(int index, int count, int subsequenceCount)
{
	if (index == subsequenceCount) {
		int sum = 0;
		for (int i = 0; i < subsequenceCount; i++)
			sum += subsequence[i];
		if (sum == S)
			answer++;
		return;
	}

	for (int i = count; i < N; i++) {
		subsequence[index] = num[i];
		dfs(index + 1, i + 1, subsequenceCount);
	}
}

int main()
{
	cin >> N >> S;
	for (int i = 0; i < N; ++i)
		cin >> num[i];

	for (int i = 1; i <= N; ++i)
		dfs(0, 0, i);

	cout << answer;
}

https://www.acmicpc.net/problem/2661

2661번: 좋은수열

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

www.acmicpc.net

#include <iostream>
#include <string>
using namespace std;

int N;

void dfs(int index, string s)
{
	if (index == N) {
		cout << s;
		exit(0);
	}

	for (int i = 1; i <= 3; ++i) {
		string tmp = s + to_string(i);

		bool good = true;
		for (int j = 1, k = tmp.size() - 1; j <= tmp.size() / 2; ++j, --k)
			if (tmp.substr(k, j) == tmp.substr(k - j, j)) {
				good = false;
				break;
			}

		if (good)
			dfs(index + 1, tmp);
	}
}

int main()
{
	cin >> N;
	dfs(0, "");
}

https://www.acmicpc.net/problem/9663

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

#include <iostream>
using namespace std;

int n, answer;
bool row[15], right_diagonal[30], left_diagonal[30];

// NxN 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수
// 다른 퀸이 가로, 세로, 대각선에 있으면 안된다.
void dfs(int cnt) 
{
	if (cnt == n) {
		answer++;
		return;
	}

	for (int i = 0; i < n; i++) {
		if (row[i] || right_diagonal[i + cnt] || left_diagonal[n - 1 - i + cnt])
			continue;

		row[i] = right_diagonal[i + cnt] = left_diagonal[n - 1 - i + cnt] = true;
		dfs(cnt + 1);
		row[i] = right_diagonal[i + cnt] = left_diagonal[n - 1 - i + cnt] = false;
	}
}

int main()
{
	cin >> n;
	dfs(0);
	cout << answer;
}

https://leetcode.com/problems/n-queens/description/

N-Queens - LeetCode

Can you solve this real interview question? N-Queens - The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You ma

leetcode.com

#include <vector>
#include <string>
#include <math.h>
using namespace std;

class Solution {
public:
    vector<vector<string>> answer;
    int check[9];

    bool IsValid(int row)
    {
        for (int i = 0; i < row; i++)
            if (check[row] == check[i] || abs(check[row] - check[i]) == abs(row - i))
                return false;
        return true;
    }

    void DFS(int n, int row)
    {
        if (n == row) {
            vector<string> temp;
            for (int i = 0; i < n; ++i) {
                string s = "";
                for (int j = 0; j < n; ++j)
                    s += (check[i] == j ? "Q" : ".");
                temp.push_back(s);
            }
            answer.push_back(temp);
            return;
        }

        for (int i = 0; i < n; ++i) {
            check[row] = i;
            if (IsValid(row))
                DFS(n, row + 1);
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        DFS(n, 0);
        return answer;
    }
};

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

#include <iostream>
#include <vector>
using namespace std;

int board[9][9];
vector<pair<int, int>> emptyPoint;

void dfs(int index)
{
	if (index == emptyPoint.size()) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j)
				cout << board[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}

	for (int i = 1; i <= 9; ++i) {
		pair<int, int> point = emptyPoint[index];
		bool flag = true;

		int dir[9][2]{ {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2} };
		for (int j = 0; j < 9; ++j) {
			if (board[point.first][j] == i || board[j][point.second] == i ||
				board[point.first / 3 * 3 + dir[j][0]][point.second / 3 * 3 + dir[j][1]] == i) {
				flag = false;
				break;
			}
		}

		if (flag) {
			board[point.first][point.second] = i;
			dfs(index + 1);
			board[point.first][point.second] = 0;
		}
	}
}

int main()
{
	for (int i = 0; i < 9; ++i)
		for (int j = 0; j < 9; ++j) {
			cin >> board[i][j];

			if (board[i][j] == 0)
				emptyPoint.push_back({ i ,j });
		}

	dfs(0);
}

https://leetcode.com/problems/sudoku-solver/

Sudoku Solver - LeetCode

Sudoku Solver - Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: 1. Each of the digits 1-9 must occur exactly once in each row. 2. Each of the digits 1-9 must occur exactly once

leetcode.com

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
	vector<unordered_set<int>> rows;
	vector<unordered_set<int>> cols;
	vector<unordered_set<int>> boxes;

	void solveSudoku(vector<vector<char>>& board)
	{
		rows.resize(9);
		cols.resize(9);
		boxes.resize(9);

		for (int i = 0; i < 9; ++i)
			for (int j = 0; j < 9; ++j)
				if (board[i][j] != '.')
					insert(i, j, board[i][j] - '0');

		fill(board, 0, 0);
	}

	bool fill(vector<vector<char>>& board, int i, int j)
	{
		if (i == 8 && j == 9)
			return true;
		if (j == 9) {
			i++;
			j = 0;
		}

		if (board[i][j] == '.') {
			for (int value = 1; value < 10; value++) {
				if (isValid(i, j, value)) {
					board[i][j] = value + '0';
					if (fill(board, i, j + 1))
						return true;
					board[i][j] = '.';
					erase(i, j, value);
				}
			}
			return false;
		}

		return fill(board, i, j + 1);
	}

	bool isValid(int i, int j, int value)
	{
		if (rows[i].find(value) == rows[i].end() && 
			cols[j].find(value) == cols[j].end() && 
			boxes[(i / 3) * 3 + (j / 3)].find(value) == boxes[(i / 3) * 3 + (j / 3)].end())
		{
			insert(i, j, value);
			return true;
		}
		return false;
	}

	void insert(int i, int j, int value)
	{
		rows[i].insert(value);
		cols[j].insert(value);
		boxes[(i / 3) * 3 + (j / 3)].insert(value);
	}

	void erase(int i, int j, int value)
	{
		rows[i].erase(value);
		cols[j].erase(value);
		boxes[(i / 3) * 3 + (j / 3)].erase(value);
	}
};

https://leetcode.com/problems/letter-combinations-of-a-phone-number/submissions/

Letter Combinations of a Phone Number - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<string> answer;
    string digitsToLetters[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    void makeLetters(string digits, string letters, int digitIndex) {
        if (digits.size() == digitIndex) {
            answer.push_back(letters);
            return;
        }

        int num = digits[digitIndex] - '0';
        for (int i = 0; i < digitsToLetters[num].size(); ++i)
            makeLetters(digits, letters + digitsToLetters[num][i], digitIndex + 1);
    }

    vector<string> letterCombinations(string digits) {
        if (digits != "") {
            makeLetters(digits, "", 0);
            sort(answer.begin(), answer.end());
        }

        return answer;
    }
};

https://leetcode.com/problems/generate-parentheses/

Generate Parentheses - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> answer;

    vector<string> generateParenthesis(int n) {
        parenthesisCombinations("", 0, 0, n);
        return answer;
    }

    void parenthesisCombinations(string s, int left, int right, int n) {
        if (s.length() == n * 2) {
            answer.push_back(s);
            return;
        }

        if (left < n)
            parenthesisCombinations(s + "(", left + 1, right, n);
        if (left > right)
            parenthesisCombinations(s + ")", left, right + 1, n);
    }
};

저작자표시

백 트래킹(Back Tracking)

기본 원리

문제

티스토리툴바