글 읽기 - 백트랙킹에 대해서 질문드립니다.

dydsj0920 5년 전 0

48번째 줄에 백트랙킹을 주석처럼 해석하는 것이 맞나요?

맞다면 백트랙킹에 걸리는 테스트케이스가 있을까요?

디버그 찍어보는데 저쪽에 걸리는 경우를 못찾았습니다.

//스도쿠
#include "stdafx.h"
#include <iostream>

using namespace std;

int n = 9;
int a[10][10];
//i행에 j가 있을때  c[i][j] = true;
bool c[10][10];
//i열에 j가 있을때 c[i][j] = true;
bool c2[10][10];
//
bool c3[10][10];

int square(int x, int y) {
	//정사각형에 번호를 붙여준다 0, 1, 2, 3, 4, 5, 6, 7, 8
	return (x / 3) * 3 + (y / 3);
}

bool go(int z) {
	if (z == 81) {
		printf("\n");
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				printf("%d ", a[i][j]);
			}
			printf("\n");
		}
		return true;
	}
	//행
	int x = z / n;
	//열
	int y = z % n;
	if (a[x][y] != 0) {
		return go(z + 1);
	}
	else {
		for (int i = 1; i <= 9; i++) {
			//숫자 i가 없으면
			if (c[x][i] == 0 && c2[y][i] == 0 && c3[square(x,y)][i] == 0) {
				c[x][i] = c2[y][i] = c3[square(x, y)][i] = true;
				a[x][y] = i;
				if (go(z + 1)) {
					return true;
				}
				//백트랙킹 - 위에서 a[x][y] = i로 놓고 검사했을때 false값이면 원래대로 되돌려 놓는다.
				a[x][y] = 0;
				c[x][i] = c2[y][i] = c3[square(x, y)][i] = false;
			}
		}
	}
	return false;
}

int main()
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &a[i][j]);
			if (a[i][j] != 0) {
				c[i][a[i][j]] = true;
				c2[j][a[i][j]] = true;
				c3[square(i, j)][a[i][j]] = true;
			}
		}
	}
	go(0);

	return 0;
}

gaelim 5년 전 1

질문이 정확히 어떤것인 지모르겠지만, 해당 코드는 정상적으로 수행됩니다.

그리고 답 한개만 출력할 수 있게끔 잘 설계되었습니다.

48번째 줄 바로 위 go(z+1) 위의

c[x][i] = c2[y][i] = c3[square(x, y)][i] = true; a[x][y] = i;

와 a[x][y] = 0; c[x][i] = c2[y][i] = c3[square(x, y)][i] = false;

는 백트래킹의 기본개념입니다.

gaelim 5년 전 1

전연변수이기때문에 원래대로 되돌려 놓지 않는다면 i로 그대로 남아있고

해당 i가 정답이아니여서 나온뒤 (되돌려놓지않고) 다른 분기로 들어가지만 이미 배열이 채워져있어 넘어갑니다.

따라서 제대로된 정답을 내놓지 못합니다.

예로 위에서 a[x][y]=0만 뺐다고 생각하면, c[x][i] = c2[y][i]=c3[square(x,y)[i]=false; 는 그대로 두고.

초기상태를 0 1 0 3 0.... 으로 생각하고

2 1 4 3 0... 으로 채어넣었고 그다음칸을 생각해보는데

도저히 완성될수 없을경우에 다시

0 1 0 3 0 ... 으로 돌아가서

4 1 5 3 0 ... 으로 수행되어야 됩니다.

그런데 되돌리지 않는다면

2 1 4 3 0 .. 에서 첫칸으로 빠져나갔다고 합시당. 어쩃든 처음칸은 반복문이라서 4로 넣을것입니다.

4 1 4 <-- 여기서 이미 이미 if (a[x][y]!=0) 이므로 다음칸으로 진행해버립니다.

그래서 올바른 답을 내놓지 못합니다.

dydsj0920 5년 전 0

댓글 감사합니다 많은 도움 되었습니다

dydsj0920 5년 전 0

백트랙킹은 그럼 구체적으로 어떤 상황에서 호출해야 하는건지 설명해주실 수 있나요?

완전탐색을 재귀함수로 구현할때 반드시 필요하다고 할 수 있을까요?

gaelim 5년 전 2

저는 문제를 많이 접해보지도 않아서 확실히는 몰라요.

하지만 대체로 알고리즘 분류가 DFS similar으로 되어있는 것과 백트래킹으로 되어있는 것은 확연히 달랐어요. 백트래킹도 큰틀에서 DFS similar에 포함되겠지만요...

재귀를 이용한 탐색 문제는 일반적으로 dfs처럼 트리의 노드 끝까지 탐색하는 것도 있지만...

좁은 제 식견으로 표현하자면,,, 더 다양하고 난이도 있다? 라고 생각이 들었어요. 트리형태만이 아니라, 그래프, Memoization... 대체적으로 아직 저한텐 확실히 어려운 것같고.

백트래킹의 경우 재귀 구조는 비슷하나, 문제를 트리형태 처럼 보고, 경우의 수를 선택해서 내려갔다가, 그거 아니면 다시 원래대로 돌아오고.... 조금 더 쉽고 해볼만할거같다? 라는 느낌?..ㅇ

스도쿠와 같은 문제는 다음칸에 들어갈게 없다고 판단하면 현재상태서 거슬러올라가는 게 백트래킹의 특징이였다면

아래 링크문제 (2017 삼성 SW 기출문제) 의 경우에는 재귀를 이용해 반드시 트리 노드의 끝단까지 도달해야만 의미가 있는 전형적인 완전 탐색 문제이에요. 그리고 dfs를 이용하여 풀 수 있어요.

https://www.acmicpc.net/proble...

도움이 되었을지는 모를겠습니다 ㅠ.ㅠ.

dydsj0920 5년 전 0

감사합니다. 재귀함수가 조금만 복잡해져도 어려워지는 저한테는 재귀함수에서 백트랙킹이 코드의 흐름상 언제 호출되어서 최적의 결과를 찾는지 이해하기가 쉽지가 않은거 같네요. 좋은 조언 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

백트랙킹에 대해서 질문드립니다.

dydsj0920 5년 전 0

gaelim 5년 전 1

gaelim 5년 전 1

dydsj0920 5년 전 0

dydsj0920 5년 전 0

gaelim 5년 전 2

dydsj0920 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말