11581 구호물자

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

11581번: 구호물자

구현방법: DFS (재귀함수)

 

dfs 함수 안에 도착점(N)에 도착하면 return 하는 조건을 넣었을 때 75% 까지만 완료되고 '틀렸습니다'가 반복됐는데, 딱 cycle이 발생하는지 아닌지만 확인하려고 이 조건을 지우니 맞았다.

아무튼 cycle이 존재하는지 확인하는 문제

 

memset은 cstring 헤더가 필요하다는 것도 다시 알게 된 사실

초기화 부분은 안 써도 되지만 새로운 걸 알게 돼서 써봤다._.

 

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

#define initialize(x, y) memset(x, y, sizeof(x));

using namespace std;

int N, result;
bool visited[101];
bool finished[101];
vector<vector<int>> adj;

void dfs(int u) {
	visited[u] = true;
	for (int v : adj[u]) {
		if (finished[v]) {
			return;
		}
		else if (!visited[v]) {
			dfs(v);
		}
		else if (visited[v]) {
			result = -1;
		}
	}
	finished[u] = true;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	
	int M, C;
	cin >> N;
    
	adj.assign(N + 1, vector<int>());
	initialize(visited, false);
	initialize(finished, false);

	for (int i = 1; i <= N - 1; i++) {
		cin >> M;
		while(M--) {
			cin >> C;
			adj[i].push_back(C);
		}
	}

	dfs(1);

	if (result == -1) {
		cout << "CYCLE";
	}
	else {
		cout << "NO CYCLE";
	}
}

오랜만에 코딩할 때의 노오력은 항상 처음부터 다시 공부하는 것