한풀이의 글 특성상 일기처럼 그냥 두서없이 작성하였다.




조건, 반복, 배열정도를 자유자제로 다루고 재귀함수에 대해서 어느정도 공부하고 나면 다음 단계는 정렬과 탐색이 아닌가 한다.

정렬같은 경우 직접 구현할 일이 잘 없지만 그래도 기본적인 qsort의 동작원리 정도는 이해하고 있어야 하겠지..


이 단계를 넘어서면 큐, 스택, 그래프, 트리 등 다른 자료구조들을 학습할 것이고 이와 동시에 완전탐색에 대한 이해가 필요하다.


완전탐색도 선형과 비선형탐색으로 나뉘는데 오늘 이야기할 부분은 비선형탐색에 관한 이야기이다.


비선형 탐색은 DFS와 BFS로 나뉠 수 있는데 요즘 열심히 보고 있는 부분은 DFS이다.




DFS의 백트랙킹 관련 문제들을 좀 정리해보고자 한다.


1. FloodFill기법 - 단지번호구하기, 미로찾기 등이 있으며 주로 재귀호출을 할 때 for문을 이용해서 상하좌우를 탐색했다.

2. depth로 탐색을 진행했던 문제 - n-queen와 같이 depth가 1일 때 나머지 열들을 반복문을 통해서 쭉 탐색

3. 체크할거냐 말거냐와 같이 2분법적으로 분기시켰던 문제 - 비숍문제와 같이 일반적으로 많이 사용하는 방법으로 시작점을 기준으로 다음 점을 체크하거나 체크하지 않거나를 기준으로 분기해서 나가는 구조



사실 구조를 나누기가 불필요할 수 있지만 나같은 초보 및 미 숙련자들에게는 DFS, 백트랙문제라고 해서 모두 같은 유형의 백트랙문제가 아니라고 생각하기 때문에 어느정도 구조를 나눠본 것이다.

수많은 고수들 처럼 나도 비선형 구조의 전체탐색 문제를 쉽게 푸는 날이 왔으면 좋겠다.


비선형구조의 전체탐색에 시간을 많이 들이는 이유는 TimeLimited가 걸릴 수는 있지만 거의 대부분의 문제의 해답을 구할 수 있는 방법이기 때문이다.

저작자 표시 비영리 변경 금지
신고

1. n-queen 문제 (출처: 문제해결을 위한 창의적 알고리즘 - 채점은 koistudy.net에서 가능)





 

  이 문제는 정보과학에서 깊이우선 탐색을 가장 대표하는 문제라고 할 수 있다. 하지만 이해하는 것은 쉽지 않으며 이 문제가 처음 깊이 우선 탐색을 접하는 학생들에게는 큰 장벽이 될 수 있다. 기본적으로 비선형 구조의 전체탐색방법인 백트랙킹 기법을 사용한다.  n의 크기가 9이하로 작기 때문에 재귀호출을 통한 전체 탐색을 진행해서 Queen의 수를 구하면 되겠다.





2. n-queen 문제 구체적 해법


  우선 퀸의 움직임에 대해서 이해해야 하는데 퀸은 상하좌우대각선 모든 칸을 움직일 수 있다. 그렇기 때문에 어느 임의의 자리에 퀸을 배치하면 다음 퀸은 첫번째 퀸의 상하좌우대각선을 제외한 곳에만 퀸을 놓을 수 있다.


  이 문제를 풀기 위해 우리는 다음과 같은 방법을 활용한다.

  1) 첫 번째 행, 첫 번째 열에 퀸을 놓는다.

  2) 다음 행으로 넘어가서 퀸을 놓을 수 있는 가장 왼쪽 칸에 퀸을 배치한다.

  3) n번째 열에 더 이상 퀸을 놓을 수 없다면 n개의 퀸을 놓을 수 없기 때문에 백트랙한다.

  4) 마지막 행에 퀸을 놓으면 하나의 해를 구한 것이다. 그리고 다시 다음 해를 구하기 위해 백트랙한다.

  5) 모든 경우를 조사할 때까지 백트랙해가며 해를 구한다.


  위의 방법대로 문제를 풀기 위해서 우리는 퀸을 놓을 수 없는 조건에 대해서 이해가 필요하다. 퀸을 놓을 수 없는 조건은 다음과 같다.

  1) 이미 퀸이 놓여진 열은 퀸을 놓을 수 없다.

  2) 퀸의 기울기 증가 대각선( / )방향에는 다른 퀸을 놓을 수 없다.

  3) 퀸의 기울기 감소 대각선( \ ) 방향에는 다른 퀸을 놓을 수 없다.



    1) 이미 퀸이 놓여진 열은 퀸을 놓을 수 없다.

현재 퀸이 어떤 열에 놓여졌는지 체크를 하기 위한 배열을 하나 만든다.

예를 들어, n=4라면 아래와 같은 표를 만들고 queen을 놓을 때마다 해당 열에 체크를 하는 것이다. 만약 1행 1열에 퀸을 놓았다면

1

 

 

 

이어서 2행 3열에 놓았다면 

1

 

1

 

이렇게 퀸을 놓을때마다 체크배열을 만들어서 체크를 하고 백트랙할 때는 체크를 지워주는 것이다.




    2) 퀸의 기울기 증가 대각선( / )방향에는 다른 퀸을 놓을 수 없다.

기울기 증가 대각선방향의 칸들은 공통적으로 x, y값의 합이 항상 일정함을 알 수 있다.


  그렇기 때문에 현재 어느 대각선에는 놓을 수 없는지 체크하기 위해 x,y값의 합(x+y)을 나타내는 배열을 하나 만들고 퀸을 놓을 때마다 해당 배열에 체크를 한다.

 

 

 

 

 

 1

 

 

 

 1

 

 

 

 

 

 

 

 

 

 

  마찬가지로 백트랙을 할 때는 체크를 지워주도록 한다.




    3) 퀸의 기울기 감소 대각선( \ ) 방향에는 다른 퀸을 놓을 수 없다.

         기울기 감소 대각선은 아래 표를 보면 알 수 있지만 두 값의 차가 항상 일정함을 알 수 있다. 하지만 한 값에서 다른 한 값을 빼면 음수가 나오는 경우도 있기 때문에 양수로 처리하기 위해 n-(x-y)을 나타내는 배열을 만들 것이다.


      이렇게 3개의 배열을 체크배열로 만들어서 퀸을 놓을 수 있는지 없는지 따져보고 놓을 수 없다면 백트랙 하도록 한다.






3. n-queen 문제 해답코드

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

int N;
int cnt;
int col[100], ic[200], dc[200];


void dfs(int r){
    if(r>N){
        cnt++;
        return;
    }
    for(int i=1; i<=N; i++){
        if(!col[i] && !ic[r+i] && !dc[N-(r-i)]){
            col[i]=ic[r+i]=dc[N-(r-i)]=1;
            dfs(r+1);
            col[i]=ic[r+i]=dc[N-(r-i)]=0;
        }
    }
}

int main()
{
    scanf("%d", &N);
    dfs(1);
    printf("%d", cnt);
    return 0;
}

//다른 버전
#include <iostream>
#include <cstdio>
using namespace std;
int N;
int ans;

int col[20], in[40], de[40];

void f(int y, int x){
    //방문이 되는가? 체크
    if(col[x] || in[y+x] || de[N+(y-x)]){
        return;
    }
    if(y==N){
        ans++;
        return;
    }
    //방문이 되므로 체크하기
    col[x]=in[y+x]=de[N+(y-x)]=1;
    //해당행에서 1~N까지 방문하기
    for(int i=1; i<=N; i++){
           f(y+1, i);
    }
    //리턴되어 나오면서 방문 체크 해제하기 (백트랙 흔적 제거)
    col[x]=in[y+x]=de[N+(y-x)]=0;
}

int main()
{
	scanf("%d", &N);
    for(int i=1; i<=N; i++){
        f(1, i);
    }
    printf("%d", ans);

    return 0;
}



저작자 표시 비영리 변경 금지
신고

1. 두더지굴 문제, 단지 구하기 문제와 같음(출처: 문제해결을 위한 창의적 알고리즘)




 

  이 문제는 깊이우선 탐색을 통한 flood fill을 수행하는 문제라 할 수 있다. 기본적으로 비선형 구조의 전체탐색방법인 백트랙킹 기법을 사용한다.  n의 크기가 30이하로 작기 때문에 재귀호출을 통한 깊이우선 탐색을 진행해도 별 무리는 없지만 만약 n이 커진다면 너비우선 탐색으로 문제를 해결할 수도 있다.


  이 문제는 우선 깊이우선 탐색으로 전체탐색을 구현할 수 있는지,

  내림차순 정렬을 할 수 있는지를 물어보는 문제라 할 수 있다.




#include <iostream>
#include <cstdio>
#include <algorithm>
int map[40][40];
int a[500];
int n, t=1;
int dx[4]={0, 1, 0, -1};    // 4방향 탐색을 반복문을 통해서 처리하기 위한 배열
int dy[4]={-1, 0, 1, 0};

using namespace std;

bool cmp(int a, int b){ return a>b; }   // 내림차순을 위한 비교함수

void dfs(int y, int x){
    if(map[y][x]==0)    return;
    a[t]++;
    map[y][x]=0;

    for(int i=0; i<4; i++){     // 상하좌우 4방향 탐색을 위한 반복문
        dfs(y+dy[i], x+dx[i]);
    }
    return;
}


int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
	    for(int j=1; j<=n; j++){
            scanf("%1d", &map[i][j]);
	    }
	}
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(map[i][j]==1){
                dfs(i,j);
                t++;
            }
        }
    }

    printf("%d\n", t-1);
    sort(a+1, a+t, cmp);        //stl을 활용한 내림차순 정렬
    for(int i=1; i<t; i++){
        printf("%d\n", a[i]);
    }
    return 0;
}




저작자 표시 비영리 변경 금지
신고

+ Recent posts

티스토리 툴바