Uva 11902 - Domanitor

Problem link

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=229&problem=3053&mosmsg=Submission+received+with+ID+20625091

Description Problem

  위 문제는 시작점이 무조건 0이고, '지배하다'의 뜻만 이해하면 된다. 노드 x가 노드 y를 지배한다면 다음을 만족해야된다. 0 에서 x를 거치지 않고서는 y로 갈 수 없다. 즉, y로가는 모든 경로는 x를 거쳐야 된다.

Algorithm to Solve Problem

  해당 문제를 해결하기 위하여 DFS(Depth first Search)알고리즘을 이용한다.

해당 문제에서 x가 y를 지배할 경우 x를 거치지 않고서는 y에 도달 할 수 가없다. 이부분에 중점을 두고 DFS 알고리즘을 조금 변형하면 현재 문제를 쉽게 해결할 수 있다.

1. 시작점을 0으로 해서 DFS를 시작하고 0에서 도달 가능한 노드들을 체크해둔다. 이사실은 배열에저장한다.

2. Dominator 즉, 지배자인지 아닌지를 확인할 정점(target)들을 순회하며 변형된 DFS를 시행한다. 변형된 DFS는 노드 0 에서 시작하며 target을 만나면 순회를 그만두고 리턴한다. 이는 그래프에서 target노드 그리고 target과 연결된 모든 간선을 제거하고 DFS 실행한 것과 동치가 된다.

3. 2번 작업이 끝나고 visited를 확인한다 visited는 DFS도중에 해당 정점에 도달했는지의 여부를 저장해놓은 배열이다. 만약 해당 정점에 도달 하지 않았고 1.에서 0에서 도달가능한 정점이라면 해당 정점은 target에 지배당한다. 

Analysis Time Complexity

  1.번 작업은 O(V + E) 소요. 여기서 V는 정점의 갯수, E는 간선의 갯수이다. 그리고 각각의 정점을 target으로 설정하고 0을 시작점으로 DFS를 한번씩 수행한다. 여기에 해당되는 시간복잡도는 O(V * (V + E)) 이다. 이때 한번의 DFS가 끝날때마다 정체 정점들을 순회하며 현재 target이 어느 정점의 지배자인지 확인하다. 그렇게 되면 최정적인 시간복잡도는 O(V + E) + O(V * (V + E + V) 이다. 이를 정리하면 O(V^2 + VE)가 된다.

Solution for the Problem as Code

#include<cstdio>

#include<vector>

#include<string>

#include<iostream>

using namespace std;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef vector<char> vc;

typedef vector<vc> vvc;

vvi graph;

vvc dominator;

vi reachable, visited;

void canReach(int here);

void dfs(int here, int t);

int main() {

int cases, cnt = 1, n;

scanf("%d", &cases);

while (cases--) {

scanf("%d", &n);

graph.assign(n, vi());

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) {

int temp; scanf("%d", &temp);

if (temp == 1)

graph[i].push_back(j);

}

//시작점으로 부터 도달할 수 있는지의 여부를 저장

reachable.assign(n, 0);

visited.assign(n, -1);

canReach(0);

dominator.assign(n, vc(n, 'N'));

//0에서 시작해서 target을 거치지 않고 dfs

//이때 reachable[x]가 1이면서 visited[x] 가 -1인

//노드x는 target에 지배 당한다.

for (int target = 0; target < n; ++target) {

visited.assign(n, -1);

dfs(0, target);

for (int i = 0; i < n; ++i) {

if (visited[i] == -1 && reachable[i])

dominator[target][i] = 'Y';

}

}

string bridge;

bridge += '+';

for (int i = 0; i < 2 * n - 1; ++i)

bridge += '-';

bridge += '+';

printf("Case %d:\n", cnt);

for (int i = 0; i < n; ++i) {

cout << bridge << endl;

for (int j = 0; j < n; ++j) 

printf("|%c", dominator[i][j]);

printf("|\n");

}

cout << bridge << endl;

++cnt;

}

}

//0부터 시작해서 도달할수 있는 정점x는 reachable[x]에 표시

void canReach(int here) {

reachable[here] = 1;

visited[here] = 1;

for (int i = 0; i < (int)graph[here].size(); ++i) {

int there = graph[here][i];

if (visited[there] == -1) {

canReach(there);

}

}

}

void dfs(int here, int t) {

if (here == t) return;

visited[here] = 1;

for (int i = 0; i < (int)graph[here].size(); ++i) {

int there = graph[here][i];

if (visited[there] == -1)

dfs(there, t);

}

}