백트래킹 문제
1. 백트래킹이란 ?
백트래킹(Backtracking)은 모든 가능한 경우의 수를 탐색하면서, 조건에 맞지 않으면 더 깊게 들어가지 않고
즉시 돌아가는(되돌아가는) 알고리즘. 완전탐색의 일종이면서 불피룡한 탐색을 줄이기 위해 가지치기를 하는 방식.
2. 어떻게 백트래킹 문제인지 판단할 수 있을까 ?
- 모든 경우를 구하라고 할 때
- 조건을 만족하는 경우만 출력해야 할때
- 주어진 수(N)이 작을 때
- 답이 여러개일 수 있을때
3. 백트래킹은 어떤 경우에 효율적일까 ?
가능한 경우의 수가 너무 많아서 전부 탐색하면 시간이 오래 걸릴 때, 조건에 맞지 않으면 되돌아감으로써
성능을 향상시킬 수 있다.
4. 백트래킹 문제라고 판단된다면 ?
- DFS 함수 정의 ( 고를 수 있는 것을 파악한 후)
- 조건 완성 시점 정의
- 조건에 따라 반복문으로 경우의 수 탐색
- 가지치기(조건에 따라) 추가
* 첫 번째 문제를 풀고 정리해 봤습니다.
코딩테스트 : 15649번 N과 M (1)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
public class BackJoon
{
private static int[] nm;
private static int n;
private static int m;
private static bool[] visited;
private static int[] result;
public static void Main()
{
nm = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
n = nm[0];
m = nm[1];
visited = new bool[n+ 1];
result = new int[m];
Permutation(0);
}
public static void Permutation(int count)
{
if (count == m)
{
Console.WriteLine(string.Join(" ", result));
return;
}
for (int i = 1; i <= n; i++)
{
if (!visited[i])
{
visited[i] = true;
result[count] = i;
Permutation(count+1);
visited[i] = false;
}
}
}
}
생각보다 시간이 더 오래걸렸고, 끝내 풀지 못해서 GPT 강사님의 힌트를 받고서야 풀었다.
계속 N과 M 그리고 visited랑 result 관련된 것들을 다 매개변수로 받아서 풀었었는데 static 변수로 선언해서 풀어도 됐다.
처음에는 애초에 재귀로 풀 생각을 못하고 있었다.
다음에도 이런 문제를 만나면 어떻게 할 것인가 ? 생각해보면
우선 총 N과 M의 수가 8로 제한되어 있기에 이정도면 전부 다 탐색해도 풀 수 있겠는데 ? 라고 생이 들면
재귀로 모든 것을 탐색하는 방향으로 떠올려 봐야겠다.
코딩테스트 : 9663번 : N - Queen
| 10 초 | 128 MB | 133869 | 64910 | 41683 | 46.802% |
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
public class BackJoon
{
static int n = int.Parse(Console.ReadLine());
private static int answer = 0;
public static void Main()
{
bool[,] board = new bool[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
board[i, j] = true;
}
}
Queen(board, 0);
Console.WriteLine(answer);
}
// 반복할 코드( 완전 탐색 - 백트래킹 )
public static void Queen(bool[,] board, int count)
{
if (count == n) answer++;
for (int row = 0; row < n; row++)
{
for (int col = 0; col < n; col++)
{
if (board[row, col])
{
board[row, col] = false;
board = diagonal(board, (row, col));
Queen(board, count + 1 );
}
}
}
}
public static bool[,] diagonal(bool[,] board, (int, int) location)
{
// 위까지 검사할 필요는 없음, 왜 ? 위에서부터 훑으면서 내려올 것이기 때문에
// 그럼 왼쪽 아래와 오른쪽 아래 대각선을 검사하자
(int,int) tempLeftLocation = (location.Item1, location.Item2);
while (tempLeftLocation.Item1 < n - 1 && tempLeftLocation.Item2 > 0 )
{
tempLeftLocation.Item1++;
tempLeftLocation.Item2--;
board[tempLeftLocation.Item1, tempLeftLocation.Item2] = false;
}
(int, int) tempRightLocation = (location.Item1, location.Item2);
while (tempRightLocation.Item1 < n - 1 && tempRightLocation.Item2 < n -1 )
{
tempRightLocation.Item1++;
tempRightLocation.Item2++;
board[tempRightLocation.Item1, tempRightLocation.Item2] = false;
}
return board;
}
}
처음에 이렇게 했다 뭘 넣어도 답이 1이 나오길래 당황했다.
생각해보니 배열은 참조타입이라 초기화를 해주어야 했다. 튜플이 참조타입인지는 검색해보고 막상 알고 있었던
배열이 참조 타입인 것을 까먹었다는게...아이러니하다.
아니 퀸이 어디든 이동할 수 있는 거였네. 나 바보같이 비숍으로 생각하고 있었다.
그래서 코드를 다시 짰다. 그래도 내용은 비슷하다.
public class BackJoon
{
static int n = int.Parse(Console.ReadLine());
private static int answer = 0;
public static void Main()
{
bool[,] board = new bool[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
board[i, j] = true;
}
}
Queen(board, 0);
Console.WriteLine(answer);
}
// 반복할 코드( 완전 탐색 - 백트래킹 )
public static void Queen(bool[,] board, int row)
{
if (row == n)
{
answer++;
return;
}
for (int col = 0; col < n; col++)
{
if (board[row, col])
{
List<(int, int)> changed = new List<(int, int)>();
board[row, col] = false;
(board, changed) = MoveQueen(board, (row, col));
Queen(board, row + 1);
board[row, col] = true;
ReMoveQueen(board, changed);
}
}
}
public static (bool[,], List<(int, int)>) MoveQueen(bool[,] board, (int, int) location)
{
List<(int, int)> changed = new List<(int, int)>();
// 위까지 검사할 필요는 없음, 왜 ? 위에서부터 훑으면서 내려올 것이기 때문에
// 그럼 왼쪽 아래와 오른쪽 아래 대각선을 검사하자
(int, int) tempLeftDiagonal = (location.Item1, location.Item2);
while (tempLeftDiagonal.Item1 < n - 1 && tempLeftDiagonal.Item2 > 0)
{
tempLeftDiagonal.Item1++;
tempLeftDiagonal.Item2--;
if (board[tempLeftDiagonal.Item1, tempLeftDiagonal.Item2] == true)
{
board[tempLeftDiagonal.Item1, tempLeftDiagonal.Item2] = false;
changed.Add((tempLeftDiagonal.Item1, tempLeftDiagonal.Item2));
}
}
(int, int) tempRightDiagonal = (location.Item1, location.Item2);
while (tempRightDiagonal.Item1 < n - 1 && tempRightDiagonal.Item2 < n - 1)
{
tempRightDiagonal.Item1++;
tempRightDiagonal.Item2++;
if (board[tempRightDiagonal.Item1, tempRightDiagonal.Item2] == true)
{
board[tempRightDiagonal.Item1, tempRightDiagonal.Item2] = false;
changed.Add((tempRightDiagonal.Item1, tempRightDiagonal.Item2));
}
}
(int, int) tempRight = (location.Item1, location.Item2);
while (tempRight.Item2 < n - 1)
{
tempRight.Item2++;
if (board[tempRight.Item1, tempRight.Item2] == true)
{
board[tempRight.Item1, tempRight.Item2] = false;
changed.Add((tempRight.Item1, tempRight.Item2));
}
}
(int, int) tempbottom = (location.Item1, location.Item2);
while (tempbottom.Item1 < n - 1)
{
tempbottom.Item1++;
if (board[tempbottom.Item1, tempbottom.Item2] == true)
{
board[tempbottom.Item1, tempbottom.Item2] = false;
changed.Add((tempbottom.Item1, tempbottom.Item2));
}
}
return (board, changed);
}
public static void ReMoveQueen(bool[,] board, List<(int, int)> changed)
{
foreach ((int, int) change in changed)
{
board[change.Item1, change.Item2] = true;
}
}
}
성공은 했지만 매우 찝찝하다... 분명 더 효율적으로 할 수 있는 방법이 있을 듯 하다.
다른 사람의 흥미로운 풀이
내 풀이는 3500자였고, 500자 밑으로 푸신 분도 있다.
조금 더 코드를 간단하게 하려면, 다음과 같은 점을 더 생각해 봐야 한다.
1. 퀸은 가로, 세로 , 대각선 방향으로 모두 움직일 수 있다.
- 1 가로 관련
한 row에 한 개의 퀸만 놓을 수 있다는 뜻이며 위에서 풀었던 방식처럼 row를 기준으로 Count ( 몇 번째 반복인지 ) 를 알 수 있다는 뜻이다. 전 코드 ( 비숍이라고 생각했을 때 ) 는 모든 row/col을 돌면서 진행했었는데 이제는 아니다. col을 모두 돌아가면서 퀸을 놓고, 다음 줄에 퀸을 놓는 것을 반복하면 된다.
-2 세로 관련
한 번 세로열 ( 특정 Col)을 사용하면 다시 사용할 수 없다.
-3 대각선 관련
이 부분을 내가 해결하지 못해서 코드가 굉장히 길어졌던 것이다.
배열에서 왼쪽 대각선, 오른쪽 대각선을 모두 제거해버렸는데 대각성의 특성을 이용하면 2차원 배열을 사용할 필요 없이,
배열 한 줄만으로도 해결이 가능하다.
우하향하는 대각선의 특징은 row + col의 값이 항상 같다 그래서 row + col의 배열 ( 일차원 ) 을 만들고 검사한다.
좌하향하는 대각선의 특징은 row - col의 값이 항상 같다. 또 다른 배열을 하나 더 만들고 검사한다.
즉 , 세로열을 검사하는 배열, 대각선을 검사하는 배열 두 개를 통해서 중복검사가 가능하게 된다.
* 주의 : row - col을 할 때는 음수가 나올 수 있기 때문에 offset을 설정해 주어야 한다.
'코딩테스트' 카테고리의 다른 글
| 2447번 별 찍기 -10, 11792번 하노이 탑 이동 순서 (0) | 2025.03.09 |
|---|---|
| 24060번 알고리즘 수업 병합 정렬 -1 , 4779번 칸토어 집합 (1) | 2025.03.03 |
| 1010번 다리 놓기 , 2018번 통계학 , 20920번 영단어 암기는 괴로워 (0) | 2025.02.26 |
| 비밀 코드 해독, 2884번 알람 시계, 가장 많이 받은 선물 (0) | 2025.02.23 |
| 신고 결과 받기, 택배 상자 꺼내기, [PCCP 기출문제] 1번 / 동영상 재생기 (0) | 2025.02.21 |