graph, dfs 1

문제는 더블릿 16 graph, dfs에 있는 dfs입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/dfs/dfs.php?pname=dfs

그래프가 주어졌을 때 시작 정점부터 시작해서 dfs 방식으로 모든 정점을 돌며 각 정점을 출력하는 문제입니다.

문제를 풀기위해 가장 먼저 생각나는건 입력 예처럼 입력이 주어졌을 때 앞 -> 뒤로 갈 수 있는 것 뿐만 아니라 뒤 -> 앞으로도 방향성을 알 수 있어야 하고 이전에 방문했던 정점의 위치를 표시해야한다는 것입니다.  

그러기 위해 2차원 배열 하나와 1차원 배열 하나씩 선언해 줍니다.

1차원 배열은 해당 정점을 인덱스로 보고 방문은 했는지 표시하며 2차원 배열은 앞 -> 뒤, 뒤 -> 앞의 방향성을 표시합니다.  

입력이 끝이 아닐 때까지 받으라는 말이 있는데 한번 정리를 하면

int n, var[10];

while(scanf("%d", &n)!=EOF){

var[i++]=n;

}

다음과 같이 사용하면 됩니다.  n이 EOF가 아니면 그 값을 사용하고 EOF이면 while문을 실행하지 않고 빠져나갑니다.

이제 앞 정점과 뒤 정점을 받을 때 2차원 배열의 각 인덱스에 표시해줍니다.  거꾸로도 마찬가지로 해줍니다.  그리고 재귀를 사용하는데 시작정점을 시작으로 2차원 배열[앞][뒤]가 방문할 수 있는 경우와 이전에 방문하지 않았을 경우 해당 뒤 정점을 시작 정점으로한 재귀를 사용합니다.