알고리즘 7 - 4: 그림 의 옮 겨 다 니 기 - 깊이 우선 검색

제목 설명
깊이 우선 검색 트 리 와 유사 한 뿌리 를 옮 겨 다 니 는 것 은 트 리 의 먼저 뿌리 를 옮 겨 다 니 는 홍보 입 니 다.그 과정 은 초기 상태 가 그림 의 모든 정점 이 방문 되 지 않 았 다 고 가정 하면 깊이 우선 검색 은 그림 의 특정한 정점 v 에서 출발 하여 이 정점 을 방문 한 다음 에 v 의 방문 되 지 않 은 인접 점 에서 깊이 우선 그림 을 옮 겨 다 닐 수 있 습 니 다. 그림 에서 v 와 경로 가 통 하 는 모든 정점 이 방문 할 때 까지.만약 에 그림 에 정점 이 방문 되 지 않 았 다 면 그림 에 방문 되 지 않 은 정점 을 시작 점 으로 선택 하고 상기 과정 을 반복 하 며 그림 의 모든 정점 이 방문 되 었 을 때 까지 반복 합 니 다.
이 문제 에서 그림 이 없 는 인접 행렬 (즉 배열 표시) 을 읽 고 방향 이 없 는 그림 을 만 들 고 상기 설명 에서 의 알고리즘 에 따라 모든 정점 을 옮 겨 다 니 며 출력 이 정점 을 옮 겨 다 니 는 순서 입 니 다.
 
 
입력
입력 한 첫 줄 은 정수 n 을 포함 하고 그림 에 n 개의 정점 이 있 음 을 나타 낸다.그 중 n 은 50 을 넘 지 않 는 다.
이후 n 줄 마다 n 개의 빈 칸 으로 구 분 된 정수 0 또는 1 이 있 고 i 줄 의 j 번 째 0 또는 1 에 대해 1 은 i 번 째 정점 과 j 번 째 정점 이 직접 연결 되 어 있 음 을 나타 내 며 0 은 직접 연결 되 지 않 았 음 을 나타 낸다.i 와 j 가 같 을 때 대응 하 는 정 수 는 0 이다.
입력 은 인접 행렬 이 대칭 행렬 임 을 보증 합 니 다. 즉, 입력 한 그림 은 반드시 방향 이 없 는 그림 입 니 다.
 
출력
한 줄 만 있 고 n 개의 정 수 를 포함 하 며 제목 설명 에 있 는 깊이 에 따라 전체 그림 의 방문 정점 순 서 를 우선 시 합 니 다.정수 마다 빈 칸 을 출력 하고 줄 끝 출력 줄 바 꾸 기 에 주의 하 십시오.
 
샘플 입력

4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0

 
샘플 출력

0 1 3 2 

AC 코드
#include #define N -99999 int a[55][55]; void str(int n,int i) {     int j;     for(j=0;j     {         if(a[i][j]==1)         {             printf("%d ",j);             a[i][j]=N;             a[j][i]=N;             str(n,j);         }     }          } int main() {     int n,i,j;     scanf("%d",&n);     for(i=0;i     {         for(j=0;j         scanf("%d",&a[i][j]);     }          printf("0 ");     str(n,0);     printf("");          return 0; }