[C] 1260: DFS와 BFS

거의 1년만에 자료구조 관련 문제를 푸느라 그런지

정말 오래걸렸다.. 그래도 어찌됐는 풀긴 했는데

일단 잠시 정리를 해봐야겠다

 

일단 DFS 관련 구현이 훨씬 쉽다.

가장 깊게 들어갔다가 그 노드가 leaf면 바로 뒤로 나오면 되기 때문에

사실상 함수를 만들어 재귀로 만든다면 바로 구현 가능하다.

 

문제는 BFS인데 얘는 같은 depth인 애부터 먼저 찾아줘야 하기때문에

재귀를 이용해서 푼다면 포인터를 쓰며 굉장히 어렵게 풀어야한다.

구조체를 만들어 서로 link해주면 될 것 같긴한데 사실상 비효율적이다.

 

이때 BFS와 관련해서 Queue를 하나 만들어주면 front에서는 삭제가, rear에서 삽입이 되면

쉽게 풀 수 있다.

특히 front와 rear이 같아지게 되는 경우는 곧 rear이 더 이상 새로운 값을 받지 않는 곳이고, queue 배열에 더 이상 추가되는 값이 없는 경우가 된다. 또 rear은 값이 추가되는 만큼, front는 while문이 돌아갈때 커진다는 것을 통해 구현 가능하다.

 

사실 이렇게 구현하는거 외에 구조체를 이용해서 푸는 방법도 있는데 일단 이건 다음에 해야겠다.

 

구현을 할때 https://studydevseung.tistory.com/13 여기에서 많은 도움을 얻었다

 

#include <stdio.h>

int arr[1001][10001]; //정점들끼리 만나는 것을 저장!
int visit[1001]; //정점을 지나갔으면 1로 바뀜
int visit_bfs[1001];
int result[1001]; //0을만나면 그만두게 만듦, 정점의 순서를 저장!
int queue[1001];

void dfs(int arr[][10001],int V,int n,int visit[],int result[],int *cnt)
{
  if((*cnt)>=n ) 
    return;
  for(int i=1;i<=n;i++)
    {
      if(arr[V][i]==1&&visit[i]==0) //정점들끼리 연결되어 있고 아직 안지나감!
      {
        visit[i]++; //이 정점을 지나감
        result[++(*cnt)]=i; //정점의 순서 저장
        dfs(arr,i,n,visit,result,cnt);        
      }      
    }
}



  int main(void)
  {
    int n,k,V;
    scanf("%d %d %d", &n,&k,&V);
    for(int i=1;i<=k;i++)
      {
        int tmp1,tmp2;
        scanf("%d %d",&tmp1,&tmp2);
        arr[tmp1][tmp2]=1;
        arr[tmp2][tmp1]=1;
      }
    int cnt2=1;
    visit[V]=1;
    result[1]=V;
    dfs(arr,V,n,visit,result,&cnt2);
      // printf("들어옴?2\n");
    
    int i=1;
    while(result[i]!=0)
      {
        printf("%d ",result[i]);
        i++;
      }
     printf("\n");


    //여기서부터 bfs
    visit_bfs[V]=1;
    printf("%d ",V);   
    queue[1]=V;
    int front=1,pop;
    int rear=2;
    
    while(front<rear) //front와 rear이 같아지게 되는 경우는 곧 rear이 더 이상 새로운 값을 받지 않는 곳이고, queue 배열에 더 이상 추가되는 값이 없는 경우가 된다. 
//rear은 값이 추가되는 만큼, front는 while문이 돌아갈때 커진다
      {
        pop=queue[front]; //queue의 현재 가장 앞에 있는 값을 꺼냄!
        front++; //front는 증가
        for(int i=1;i<=n;i++)
          {
            if(arr[pop][i]==1&& visit_bfs[i]==0) // 그 값에서 갈 수 있는 경우를 구함
            {
              printf("%d ",i);
              queue[rear++]=i; //값이 추가될 때마다 queue는 한 칸 늘어남
              visit_bfs[i]=1;
            }
          }
      }

    return 0;
    
  }