'알고리즘'에 해당되는 글 1건

#include<stdio.h>

bool connection[50][50]={0,};

bool visit[50];

int np,nw;

void dfs(int);

int main() {

    int d1,d2;

    printf("How many Points?");

    scanf("%d",&np);

    printf("How many ways?");

    scanf("%d",&nw);

    printf("\n");

    for(int i=0;i<nw;i++){

        scanf("%d %d",&d1, &d2);

        connection[d1][d2] = connection[d2][d1] = true;

    }

    dfs(1);

}

void dfs(int start)

{

    visit[start] = true;

    printf("Visited %d\n",start);

    for(int i=0;i<np+1;i++)

    {

        if(connection[start][i])    

            if(!visit[i])

                dfs(i);

    }

    return;

}

는 start (현재 점) 과 i (이동하려는 점)이 연결되어 있는지를 봅니다.

는 i (이동하려는 점)이 이미 방문되었는지를 확인합니다.

따라서 실질적인 이동을 하는 위의 코드는 연결되어 있는 점이 방문된 적이 없을 때만 실행되게 됩니다.

DFS는 일단 한 점에서 시작해서 들어갈 수 있는 곳까지 계속 들어가면서 탐색하는 것입니다. 따라서 위의 방법대로 하면 한 점에서 이동가능한 점으로 이동하고 또 그 점에서 이동가능한 점으로 이동하면서 계속 들어가게 됩니다.