EVO

이 문제는 DFS 알고리즘을 사용하여 사이클을 이루지 않는 사람의 수를 구하는 문제 입니다. 내 풀이 방향그래프에서의 사이클이 존재하는 지의 여부는 간선 구분을 통해 판정할 수 있습니다. 사이클이 존재한다는 것은 역방향 간선의 여부와 동치인데 그전에 역방향간선에 대해 간단하게 살펴보자면 그래프에서 Ti부터 DFS알고리즘을 돌리면 트리형태를 띠게됩니다. 그러한 트리를 DFS 스패닝 트리라고 합니다. (Tm, Tj)의 간선은 스패닝트리의 자손에서 선조로 연결된 간선인 역방향 간선입니다. 그래서 사이클이 있는 그래프를 깊이우선탐색을 할 경우 무슨일이 벌어질지 생각해보면 쉽게 이해를 할 수 있습니다. 사이클에 포함된 정점 중 깊이 우선 탐색과정에서 처음만나는 정점을 u(Tj)라고 합시다. dfs(u)는 u에서 ..

https://www.acmicpc.net/problem/15486 남은 N일 동안 최대한 많은 상담을 하려고 한다. 쉽게 생각해보면 day[상담을 잡은 날] = ? //?: ex=3 상담을 잡은 날 + day[상담을 잡은 날] =>ex) 1+array[1] = 1+3 = 4 // 4일째부터 가능 result+=profit[상담을 잡은 날] 일단 가장먼저 생각나는 dfs를 이용한 완전탐색으로 풀어보면 #include #include #include using namespace std; int N; int day[1500001]; int profit[1500001]; int maxRes = -10000; void dfs(int 상담날짜,int 총금액) { int 금액 = profit[상담날짜]; 총금액 +..

문제 분석 예를 들어 2 2 2 4 4 4 8 8 8 이 주어지고 왼쪽으로 이동할때는 4 2 0 8 4 0 16 8 0 의 결과가 나와야 하는데 이러한 결과에 착안해서 해당입력에서 왼쪽으로 이동할때는 왼쪽부터 계산해야한다는 순서가 필요합니다. 좀더 도식화를 시키고 보면 a b c d e f h i j 왼쪽으로 이동할때 보는 순서는 (0,0)⇒(0,1): a와 b가 같을때 (0,0) = a+b (0,1) = 0 a와 b가 다를때 (0,0) = a (0,1) = b 그러나 만약 a가 0이라면 (0,0) = b (0,1) = 0 그 다음은 (0,1)⇒(0,2): b와 c가 같을때 (0,1) = b+c (0,2) = 0 b와 c가 다를때 (0,1) = b (0,2) = c 그러나 만약 b가 0이라면 (0,1) ..