DFS Algo

1. map 2. visit 3. 사용해서, 풀이 ㅇㅋ 4. depth 해서 최단 거리 구하기 5. 이렇게 문제 풀이 가능 6. 코드 분석 능력도 오케이 7. 가져다가 쓸 수 있음 8. 이후 정답 코드 문제 보기

#include <stdio.h> #define MAX 10 int map[MAX][MAX]; int visit[MAX]; int vertex; int edge; int maxEdge; int start; int end; void depthFirstSearch(int v, int depth) { int i; if (v == end) { if (maxEdge < 0 || depth < maxEdge) { maxEdge = depth; } return; } visit[v] = 1; for (i = 1; i <= vertex; i++) { if (map[v][i] == 1 && !visit[i]) { depthFirstSearch(i, depth + 1); visit[i] = 0; } } } int main() { freopen("input.txt", "r", stdin); int T, test_case, i, v1, v2; scanf("%d", &T); for (test_case = 1; test_case <= T; test_case++) { scanf("%d %d %d %d", &vertex, &edge, &start, &end); for (i = 0; i < edge; i++) { scanf("%d %d", &v1, &v2); map[v1][v2] = 1; } maxEdge = -1; depthFirstSearch(start, 0); printf("#%d %d\n", test_case, maxEdge); } return 0; }