C·C++

한붓그리기 문제: 산타할아버지 집(C++)

한붓그리기 문제: 산타할아버지 집(C++) 대표 이미지
/*
    4
  /   \
5----3
| \   /|
|  \ / |
|  /\  |
| /  \ |
|/    \|
1----2
[산타집]
산타 할아버지의 집을 한붓 그리기로 그리는 모든 방법을 출력해 보아요!
---알고리즘 요약---
DFS를 이용해 모든 경우를 검색해 본다.
*/
#include <iostream>
#include <windows.h>

using namespace std;
bool a[5][5]={{0,1,1,0,1},{1,0,1,0,1},{1,1,0,1,1},{0,0,1,0,1},{1,1,1,1,0}};
int path[9],n;
void DFS(int vertex){
     int i;
    
     path[n]=vertex;
     if(n==8){
              for(i=0;i<9;i++)cout<<path[i]+1<<" ";
              cout<<endl;
              return;
     }
    
     for(i=0;i<5;i++){
                      if(a[vertex][i]==1){
                                     a[vertex][i]=a[i][vertex]=0;
                                     n++;
                                     DFS(i);
                                     a[vertex][i]=a[i][vertex]=1;
                                     n--;
                      }
     
     }
     return;
}
                                                     
int main(){
    DFS(0);//시작점과 끝점은 당연 0아님 1이다
    DFS(1);
   
    system("PAUSE");
    return 0;
}

출력결과
1 2 3 1 5 3 4 5 2
1 2 3 1 5 4 3 5 2
1 2 3 4 5 1 3 5 2
1 2 3 4 5 3 1 5 2
          :
          :
2 5 4 3 2 1 3 5 1
2 5 4 3 2 1 5 3 1
2 5 4 3 5 1 2 3 1
2 5 4 3 5 1 3 2 1
Press any key to continue . . .
    

댓글