길찾기

1. dfs 2. 정보 저장과 visit 3. 간 길 표시, 나온 것 다시 표시 4. from, to 배열 만들 때 idx, value 저장 위치 정확하게 파악하기 5. 헷갈리지 않도록 인풋 받을 때나, 변수 명에 주의하기

#include <stdio.h> int path[2][100]; int visit[100]; int hasPath; void dfs(int cur) { if (cur == 99) // 도착 hasPath = 1; if (hasPath) return; if ((path[0][cur] != -1) && (visit[path[0][cur]]) == -1) { // 첫번째 길에 길이 있는지 확인하기 visit[path[0][cur]] = 1; dfs(path[0][cur]); visit[path[0][cur]] = -1; } if ((path[1][cur] != -1) && (visit[path[1][cur]]) == -1) { // 두번째 길이 있는지 확인하기 visit[path[1][cur]] = 1; dfs(path[1][cur]); visit[path[1][cur]] = -1; } } int main() { freopen("input.txt", "r", stdin); int T; int length; int from, to; int i; for (T = 1; T <= 10; ++T) { hasPath = 0; for (i = 0; i < 100; ++i) path[0][i] = path[1][i] = visit[i] = -1; scanf("%d %d", &T, &length); for (i = 0; i < length; ++i) { scanf("%d %d", &from, &to); if (path[0][from] == -1) path[0][from] = to; else path[1][from] = to; } dfs(0); printf("#%d %d\n", T, hasPath); } return 0; }