백준 복습 - 백트랙킹

백트랙킹 - 15649번: N과 M (1)

1) 뒤의 N과 M 문제들의 가장 바탕이되는 문제이다

-> 그렇기에 복습 필요

https://jh4995.tistory.com/162

백트랙킹 - 15649번

---

백트랙킹 - 15650번: N과 M (2)

https://jh4995.tistory.com/163

백트랙킹 - 15650번

---

백트랙킹 - 15651번: N과 M (3)

https://jh4995.tistory.com/165

백트랙킹 - 15651번

---

백트랙킹 - 15652번: N과 M (4)

https://jh4995.tistory.com/169

백트랙킹 - 15652번

---

백트랙킹 - 14888번: 연산자 끼워넣기

https://jh4995.tistory.com/173

백트랙킹 - 14888번

---

백트랙킹 - 14889번: 스타트와 링크

1) 풀이구조가 다른 백트랙킹 문제들과는 다르다

2) 그렇기에 풀이 대부분을 참고함

-> 복습필요

https://jh4995.tistory.com/177

백트랙킹 - 14889번

---

백트랙킹 - 9663번: N-Queen (23.03.29 추가)

1) 가장 대표적인 백트랙킹 문제이자, 기초적인 풀이과정

-> 자주 복습할 것

https://jh4995.tistory.com/216

[C] 백준 - 9663번: N-Queen

---

백트랙킹의 경우

주로 재귀를 통한 DFS를 진행하는 과정에서, DFS가 빠질 수 있는 비효율적인 경로를 차단하며 탐색하는 기법이다

이 문제는 DFS풀이과정에서 약간의 추가를 한 아래의 풀이를 동일하게 활용하며 진행한다

void DFS(int index)
{
	if (index == M)
	{
		for (int i = 0; i < M; i++)
		{
			printf(" ");
		}
	}

	else
	{
		for (int i = 1; i <= N; i++)
		{
			if (...)
			{
				continue;
			}
			else
			{
				...
				DFS(index + 1);
				...
			}
		}
	}
}

 

 

- 15649번: N과 M(1)

15649번 문제의 풀이에서 약간의 변화만 주면 15652번까지의 풀이가 완성되므로 15649번을 자세히 본다

먼저 백트랙킹 문제는 위에서 언급했던 것 처럼 DFS를 진행하는 것이 우선이다

그렇기에 위에 작성해놓은 void 함수의 구조를 가장 바탕으로 놓고 풀이를 진행하게된다

하지만 기존의 DFS풀이와는 다르게 index 값이 M과 같아지는 특정한 경우에만 출력을 진행하고,

그 이외의 경우에서는 다시 반복문을 돌면서 재귀를 진행한다

void DFS(int index)
{
	if (index == M)
	{
		for (int i = 0; i < M; i++)
		{
			printf("%d ", result[i]);
		}
		printf("\n");
	}

	else
	{
		for (int i = 1; i <= N; i++)
		{
			if (visited[i])
			{
				continue;
			}
			else
			{
				result[index] = i;
				visited[i] = 1;
				DFS(index + 1);
				visited[i] = 0;
			}
		}
	}
}

 

- 14888번: 연산자 끼워넣기

이 문제도 역시 위의 구조와 동일하게, 사칙연산 중 하나를 진행하는 경우 +x에 +1을 해주다가

만약 x값이 N-1과 같아지면, 그때의 sum이 max 혹은 min이 되는지 판단하고

x값이 N-1과 같지 않다면(= N-1까지 값이 커지지 않았다면), 다시 사칙연산 중 하나를 재귀를 통해 진행한다

void calculate(int plus, int minus, int multiplication, int division, int x, int sum)
{
	if (x == N - 1)
	{
		if (max < sum)
		{
			max = sum;
		}
		if (min > sum)
		{
			min = sum;
		}
	}

	else
	{
		if (plus != 0)
		{
			calculate(plus - 1, minus, multiplication, division, x + 1, sum + num[x + 1]);
		}
		if (minus != 0)
		{
			calculate(plus, minus - 1, multiplication, division, x + 1, sum - num[x + 1]);
		}
		if (multiplication != 0)
		{
			calculate(plus, minus, multiplication - 1, division, x + 1, sum * num[x + 1]);
		}
		if (division != 0)
		{
			calculate(plus, minus, multiplication, division - 1, x + 1, sum / num[x + 1]);
		}
	}
}

 

- 9663번: N-Queen

이 문제도 대표적인 백트랙킹 문제이다

추가적인 풀이가 더해져야하지만, 역시나 DFS를 진행하는 과정의 큰 틀은 위와 동일하게 사용하는 것을 볼 수 있다

void nqueen(int row) {

    // n번째 행까지 n개의 퀸을 놓는 하나의 경우의 수를 찾았다면, 함수 종료
    if (row == n) {
        cnt++;
        return;
    }
    // 모든 경우의 수를 찾지 못한 경우
    else {

        // 현재 행에서 모든 열 검사
        for (int col = 0; col < n; ++col) {

            // 행 위치에 열 값을 할당
            queen_loc[row] = col;

            // 현재 행, 열 위치가 퀸의 위치로 문제 없다면, 다음 행 검사
            if (possible_loc(row)) {
                nqueen(row + 1);
            }
            // 현재 행, 열 위치가 퀸의 위치로 문제가 있다면, 이어서 반복문 진행
        }
    }
}

 

 

백트랙킹 알고리즘 설명 참고 -> https://chanhuiseok.github.io/posts/algo-23/

9663번 풀이출처 -> https://velog.io/@mmindoong/알고리즘-백트래킹BackTracking