11581 구호물자

BOJ::11581 구호물자

https://www.acmicpc.net/problem/11581

단순히 방문여부만 체크해서 백트래킹 하니 시간초과가 났다.

그래서 좀더 깊이 생각해보니 한번 N까지 도착 한 경로를 굳이 다시 볼 필요가 없으므로,

visited를 단순히 방문,미방문 으로 놓는것이 아니라

방문,미방문,방문했고 탐색끝남 3가지 상태로 놓고 풀었더니 통과했다.

생각보다 쉽지 않아서 깊이우선탐색을 재귀,stack 두 가지 방법으로 풀어봤다.

<stack을 이용한 방법>

#include <stdio.h>
#include <stack>
using namespace std;
 
int n;
int map[101][101];
int visited[101];
bool flag;
 
void dfs(int v) {
    stack<int> s;
    s.push(v);
    visited[v] = 1;
 
    while (!s.empty()) {
        int vv = s.top();
        flag = false;
        
        for (int i = 1; i < n; i++) {
            if (map[vv][i] == 1) {
                if (visited[i]==1) {
                    printf("CYCLE\n");
                    return;
                }
                else if(visited[i]==0){
                    s.push(i);
                    visited[i] = 1;
                    flag = true;
                    break;
                }
            }
        }
 
        if (!flag) {
            visited[s.top()] = -1;
            s.pop();
        }
    }
    printf("NO CYCLE\n");
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x;
        scanf("%d", &x);
        for (int j = 0; j < x; j++) {
            int y;
            scanf("%d", &y);
            map[i][y] = 1;
        }
    }
    dfs(1);
}

<재귀를 이용한 방법>

#include <stdio.h>
using namespace std;
 
int n;
int map[101][101];
int visited[101]; // -1:탐색끝남,0:미방문,1:탐색중방문
bool flag;
 
void dfs(int v) {
    visited[v] = 1;
 
    for (int i = 1; i < n; i++) {
        if (map[v][i] == 1) {
            if (visited[i] == 1) {
                flag = true;
                return ;
            }
            else if (visited[i] == 0) {
                dfs(i);
            }
        }
    }
 
    visited[v] = -1;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x;
        scanf("%d", &x);
        for (int j = 0; j < x; j++) {
            int y;
            scanf("%d", &y);
            map[i][y] = 1;
        }
    }
 
    dfs(1);
    if (flag) {
        printf("CYCLE\n");
    }
    else {
        printf("NO CYCLE\n");
    }
}