본문 바로가기

dfs

BOJ)2275 트리의 높이 줄이기 문제: icpc.me/2275 트리에서 모든 리프까지의 거리가 H이하로 되게 만들 때 비용의 최솟값을 구하는 문제이다. 우리는 가능하다면 부모에서 높이를 줄여야지 한번에 여러 리프들의 높이를 동시에 줄이는게 가능하다는 사실을 이용하여 모든 리프에 줄여야할 가중치를 할당하고 바텀업 방식으로 부모에서 높이를 줄이는게 가능하다면 줄이는 방식으로 문제를 해결해주면 된다. 문제를 해결하기 위하여 dfs로 전처리를 해줘야하는데 해당 노드의 깊이 중첩 가중치를 미리 구해주면 쉽게 계산해 줄 수 있다. 아래 코드에서 각 배열이 의미하는건 r[v]는 v노드에서 줄여야하는 가중치이고 d[v]는 v까지의 누적 가중치이다. 123456789101112131415161718192021222324252627282930313233.. 더보기
BOJ)8012 한동이는 영업사원! 문제:icpc.me/8012 한동이가 방문해야 할 도시를 x->y->z->w 순이라면 x->y의 거리와 y->z의 거리 z->w의 최소시간을 더해서 출력하는게 답이된다. 결국 N,M제한 때문에 거리를 logN의 시간복잡도에 해결을 해줘야하는데 우리는 주어진 그래프가 트리라는걸 이용하여 LCA를 통하여 계산해 줄수 있다. x와 y의 최단 거리는 결국 모든 간선의 가중치가 1이니까 깊이를 이용하여 dph[x]+dph[y]-2*dph[lca(x,y)] 로 계산할 수 있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#in.. 더보기
BOJ)1761 정점들의 거리 문제:icpc.me/1761 두 정점간의 최단거리를 매 쿼리마다 출력하는 문제이다. 우리가 기본적으로 알고 있는 그래프의 최단거리 알고리즘들은 시간복잡도 때문에 사용할 수가 없다. 하지만 우리는 이 그래프가 트리라는것을 이용하여 매 쿼리를 O(logN) 시간마다 처리해 줄 수있다. 우리는 lca를 이용하여 두 노드의 최단 거리를 계산할 것이다. lca전처리를 위해 dfs를 돌려줄 때 루트에서 부터 자기 자신까지의 거리를 dist배열에 저장해두면 두 노드의 X,Y 의최단 거리는 dist[X]+dist[Y]-2*dist[lca(X,Y)]로 정의 할 수있다. 이를 이용하여 매 쿼리를 logN시간에 처리해주면 된다. 12345678910111213141516171819202122232425262728293031.. 더보기
BOJ)10265 MT 문제: icpc.me/10265 K이하의 사람이 버스에 탈 수 있을 때 버스에 탈 수 있는 최대 인원을 출력하는 문제이다. 문제에는 조건이 있는데 A라는 사람은 B라는 사람이 버스에 안타면 A도 반드시 안타는 정보 N개가 주어진다. 우리는 이러한 조건을 B->A라는 방향 그래프로 만들어 준 SCC끼리 분류를 한다음 다음 위상 정렬을 이용하여 X라는 정점이 방문 가능한 모든점 Y는 반드시 X의 인원을 포함한다고 정의 가능하다. 이 때 X의 인원은 SCC의 그룹 크기와 동치가 된다. 따라서 연결 그래프마다 최소 인원~최대 인원 셋을 저장한 뒤 Knapsack문제를 해결하듯이 다이나믹 프로그래밍을 이용해주어 답을 계산해주면 된다. 이때 연결 그래프의 수는 SCC 그래프의 indegree가 0인 SCC의 개수이.. 더보기
BOJ)3977 축구 전술 문제: icpc.me/3977 A->B로 이동해야하는 전술들이 주어질 때 시작 지점이 될 수 있는 위치를 찾는 문제이다. 이 때 적절한 시작지점이 없으면 Confused를 출력하면 된다. 여기서 SCC를 이루는 그룹이면 어떤 곳에서 시작하던 topology에 의해 나머지 지점들을 전부 탐색 가능하니 정점들을 SCC로 묶은 뒤 indegree가 0인 지점이 하나일 때는 해당 SCC에 속하는 모든 점들이 시작지점이 될 수 있고, 만약 indegree가 0인 지점이 여러곳일 경우에는 어떤 지점에서 시작해도 모든 점을 방문 불가능하기 때문에 Confused를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424.. 더보기
BOJ)4196 도미노 문제:icpc.me/4196 X번 블록이 넘어지면 Y번 블록이 넘어지는 정보가 여러개 주어질 때 도미노를 직접 넘어뜨려야하는 최소 블록 개수를 출력하는 문제이다. 도미노를 직접 넘어뜨려야 한다는 건 결국 다른 도미노에 의해서 넘어지지 않는다는걸 의미하는데 이는 곧 indegree가 0인 정점의 개수다. 또 하나 고려해줘야 하는 경우가 있는데 cycle을 이룰 경우 indegree가 0이지 않지만 누가 먼저 넘어지지 않는 이상 영원히 넘어지지 않는다. 따라서 우리는 방향 그래프에서 SCC를 구해준 후 SCC로 이루어진 그래프에서 indegree가 0인 SCC의 개수를 세어주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839.. 더보기
SCC(Strongly Connected Component) 방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라 칭합니다. 더 정확하게 정의하자면 SCC가 되는 그룹은 항상 최대로 정의되기 때문에 다음과 같은 조건을 만족해야 합니다. 1. 같은 SCC 내의 임의의 두 정점 A,B사이의 경로가 항상 존재한다.2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다. (SCC 끼리는 사이클이 존재하지 않는다.) SCC를 직역하면 "강한 연결 요소" 라는 뜻이됩니다. 즉 SCC는 집합 내에서 정점들이 서로 왕복 가능한 최대 크기의 집합입니다. 다음과 같은 그래프에.. 더보기
BOJ)2150 Strongly Connected Component 문제: icpc.me/2150 SCC를 구하는 기본 문제이다. 출력을 SCC가 속한 가장 작은 정점의 정점 번호 순으로 출력해야 하므로 정렬이 필요하다. 코사라주 알고리즘을 통하여 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include #include #define MAX_V 10000using namespace std;int v, e, visited[MAX_V + 1], x, y, r;vector scc;vector vt;vector rvt;stack st;bo.. 더보기
BOJ)2623 음악프로그램 문제: icpc.me/2623 음악프로그램의 출연 순서의 리스트가 주어졌을 때 모든 리스트를 만족시키도록 출연 순서를 출력하는 문제이다. 만약 모든 리스트를 만족할 수 없는 경우 0을 출력하면 된다. 우리는 출연 순서가 A->B->C 라면 A->B / B->C의 방향으로 간선을 연결해 준 뒤 topology를 구해줌으로서 리스트를 구할 수 있다. 이때 모든 리스트를 만족할 수 없는 경우는 사이클이 생기는 경우로서 그래프의 사이클 여부를 체크해줌으로서 확인 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include #define MA.. 더보기
BOJ)11438 LCA 2 문제:icpc.me/11438 이 문제는 LCA (BOJ 11437) 의 풀이도 포함한다. 루트의 번호가 1번인 N개의 정점으로 이루어진 트리가 존재할 때 두 노드의 쌍 M이 주어질 때 두 노드의 LCA를 구하는 문제이다. 여기서 LCA(Lowest Common Ancestor)란 직역하면 최소 공통 조상(?) 이다. 즉 트리의 두 노드가 주어졌을 때 서로의 조상을 거슬러올라갔을 때 가장 먼저 만나는 정점이 LCA가 된다. LCA를 구하는 방법으로 두 노드의 높이(깊이)를 맞춘후에 한칸씩 올라가며 조상이 같아질 때까지 비교하는 방법이 있다. 하지만 이방법은 한번의 쿼리를 처리할 때 O(N)의 시간복잡도를 가지므로 LCA 2문제 같이 M과 N이 10만이면 O(N*M)으로 TLE를 피하기 힘들것이다. 그래서.. 더보기