Binary Search Tree 구현을 해보았다. 

트리 만드는 부분 까지만 되어 있다.

지금은 root부터 insert로 트리를 생성하게 되어 있는데, 첨에는 다르게 해보다가 엄청 고생함.

최적화 된 형태는 아니기 때문에 향후에 업데이트 될 가능성은 크다.

인접리스트로만 구현하려고도 해봤는데, left, right가 [0], [1]로 되어야 해서 좀 어색하고,

특히 parent처리하려면 별도 배열을 쓰거나 node안에 w옆에 넣어야 하는데 좀 어색함

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct node { int parent, l, r; };
int root, c, n, u, v;
#define MAX_NODE (1000001)
 
void insert(vector<node>& tree, int n, int v) {
    if (v < n) {
        if (tree[n].l == 0) { tree[n].l = v, tree[v].parent = n; return; }
        insert(tree, tree[n].l, v);
    }
    else {
        if (tree[n].r == 0) { tree[n].r = v, tree[v].parent = n; return; }
        insert(tree, tree[n].r, v);
    }
}
int main()
{
    vector<node> tree(MAX_NODE);
    cin >> root;
    tree[root] = { -1,0,0 };
    while (cin >> n) {
        insert(tree, root, n);
    }
    return 0;
}
 
cs


이걸로 post_order로 순회하는 것까지 구현한게 아래 코드이고, 이 문제에 대한 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct node {int parent,l,r;};
int root,c,n,u,v;
vector<node> tree(1000001);
 
void post_order(int n){
    if(n==0return;
    post_order(tree[n].l);
    post_order(tree[n].r);
    cout << n << '\n';
}
void insert(int n, int v){
    if(v<n){
        if(tree[n].l==0) {tree[n].l=v,tree[v].parent=n;return;}
        insert(tree[n].l,v);
    } else{
        if(tree[n].r==0) {tree[n].r=v,tree[v].parent=n;return;}
        insert(tree[n].r,v);
    }
 
}
int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt""rt", stdin);
#endif
    cin >> root;
    tree[root] = {-1,0,0};
    while(cin >> n){
        insert(root, n);
    }
    post_order(root);
    int sdf = 1;
    return 0;
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

백준 4103 ATM  (0) 2020.05.05
백준 15481 그래프와 MST  (0) 2020.05.02
인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
Visual Studio Code  (0) 2020.04.03

그래프 문제를 풀때 인접행렬, 인접리스트를 다룰일이 워낙 많아서 별도 글로 하나 정리해 둔다.


인접행렬보다는 인접리스트로 구현하는게 일반적으로 더 나은데, 간선수가 최대일 경우 정점의 개수 제곱정도 되는데 인접행렬로 구현하게 되면 항상 이정도 복잡도를 가지는 반면 인접리스트로 구현하면 간선이 드물수록 속도 업이 된다. (예를 들어 그래프가 트리인 경우 최대 간선수는 정점의 제곱이 아닌 정점의 개수-1개 정도로 줄어든다.)


그래서 인접리스트 구현을 먼저 실어두고 나중에 PS할때 이용하려고 한다.


인접리스트 간선가중치 없는 경우

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
int N, M, u, v;
int32_t main()
{
    cin >> N >> M;
    vector<vector<int>> adj_list(N + 1);
    REP(i,M){
        cin >> u >> v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    return 0;
}
cs


인접리스트 간선가중치 있는 경우

w=1로 놓으면 간선가중치 없는 경우에도 범용적으로 쓸수 있기는 한데.. 무거울듯?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
int main()
{
    //V:정점개수, E:간선개수
    int V, E; scanf("%d%d%d"&V, &E);
    vector<vector<node>> adj_list(V + 1);
    for (int i = 0; i < E; i++) {
        int u, v, w; scanf("%d%d%d"&u, &v, &w);
        adj_list[u].push_back({ v, w });
        //adj_list[v].push_back({ u, w });  //undirected면 주석 풀 것
    }
    return 0;
}
 
 
cs



인접행렬 간선가중치 있는 경우

간선가중치 없는 경우는 단순하게 w대신 1을 넣어주면 되기 때문에 트리비얼하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 4;
int n, m, u, v, w;
int main()
{
    scanf("%d%d"&n, &m);
    vector<vector<int>> in(n+1vector<int>(n+1, INF));  // 없는간선은 INF
    // 위에가 좀 문법적으로 헤비하면 int in[1001][1001]; 이런식으로 써도 된다.초기화 별도
    for (int i = 0; i < n; i++) in[i][i] = 0;  // 자기자신은 0
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d"&u, &v, &w);
        // 간선이 여러개일경우, 최단거리 단선만 기억(인접리스트와 다르게 이처리 필수)
        // 이문제의 경우 1-base index라 1빼줌(문제에 따라 다르게 처리)
        in[u - 1][v - 1= min(in[u - 1][v - 1], w);
    }
    return 0;
}
 
cs



반응형

'Programming > Problem Solving' 카테고리의 다른 글

백준 15481 그래프와 MST  (0) 2020.05.02
BST 트리 구현  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
Visual Studio Code  (0) 2020.04.03
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02

최장거리 구하는 문제는 기본적으로 모든 정점을 다 가보고 max값 갱신해주는 형태이다.

백준 10273번 고대동굴탐사 문제처럼 최장거리 뿐 아니라 최대 이득, 최대 비용 이런식으로 비용의 문제로 출제되는 경우도 있다.


한가지 생각할 점은, 모든 정점을 다 가보는 방식이므로 DFS도 효율적이라는 점(BFS를 고집할 필요없다.)

그리고 이문제는 의외로, 방향그래프와 무방향그래프에서의 접근방법이 다른데,

방향그래프에서는 사이클이 없는 DAG이어야 구할 수 있고, 의외로 위상정렬 개념이 들어간다.

위상정렬 개념 없이는 아래와 같은 그래프에서 최장거리 구하기가 까다롭다.

사이클이 존재하는 그래프에서의 최장거리구하기 문제는 NP-Hard에 속하기 때문에PS에서는 안나온다.
모든 정점이 연결되어 있는 완전그래프에서의 최장거리는 TSP문제와 같아진다.

무방향 그래프에서도 당연히 사이클이 없는 트리와 같은 형태로만 PS문제로 주어지고, 이경우는 그냥 BFS같은거 돌리면 된다.
(단순 visit처리만 하면 됨)


사이클없는 무향그래프(트리)에서 최장거리 구하기

기본적으로 트리이거나 포레스트이므로 단순히 BFS돌리면서 max 갱신만 해주면 된다.

이 문제의 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
struct node { int v, w; };
using vvn = vector<vector<node>>;
//모든 노드로의 longest 한번에 구하기
vi longest(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    if (base1) max_v++;
    vi visit(max_v), max_dist(max_v, -1);
    queue<node> q; q.push({ start_v,0 }); visit[start_v] = 1;
    int ln = -1, ld = 0;
    while (q.size()) {
        node n = q.front(); q.pop();
        if (n.w > max_dist[n.v]) max_dist[n.v] = n.w;
        for (node adj : adj_list[n.v]) {
            if (visit[adj.v])continue; visit[adj.v] = 1;
            q.push({ adj.v, adj.w + n.w });
        }
    }
    return max_dist;
}
//최장경로 길이와 해당노드만 리턴
node longest2(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    int ln = -1, ld = 0;
    vi md = longest(max_v, start_v, adj_list, base1);
    for (int i = (int)base1; i < (int)base1 + max_v; i++)
        if (i != start_v && md[i] > ld)ld = md[i], ln = i;
    return { ln,ld };  // longest node, longest distance
}
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    //일단 인접리스트 받자
    //V:정점개수
    int V; cin >> V;
    vvn adj_list(V + 1);
    for (int i = 0; i < V - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj_list[u].push_back({ v, w });
        adj_list[v].push_back({ u, w });
    }
    node n1 = longest2(V, 1, adj_list, true);
    node n2 = longest2(V, n1.v, adj_list, true);
    cout << n2.w << endl;
    return 0;
}
cs

트리의 지름을 구하는 문제의 답안이기도 한데, 

트리의 경우는 임의의 점에서 가장 먼 노드(A)를 찾고 그 노드(A)에서 가장 먼 노드까지의 거리가 트리의 지름입니다. 이 그리디 인사이트만 있으면 풀수있다.


사이클 없는 유향그래프(DAG)에서 최장거리 구하기

이경우 위상정렬을 해야한다(in_edge처리). 이 문제의 답이기도 하다.

또한 이 코드의 경우 모든 경로에 대한 간선개수를 세는 부분도 있으니 참고하자.

보통은 from[N]배열로 단일경로는 찾을 수 있지만, 여기처럼 모든 경로를 찾으려면 max_dist를 이용한 역 탐색이 필요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
using vi = vector<int>;
using vvn = vector<vector<node>>;
//모든 노드로의 longest 한번에 구하기
vi visited(10001), max_dist(10001-1);  // 간선 카운팅 때문에 밖에 나와있다.
vi longest(int max_v, int start_v, vvn& adj_list, vi& in_edge, bool base1 = false) {
    queue<node> q;
    function<void(node)> enqueue = [&](node n) {
        if (in_edge[n.v] != 0return;
        q.push(n);
    };
 
    //start_v와 무관해도 indgree=0인 정점은 모두 넣어야, 위상정렬이 정상 진행됨
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,0 });
    vi cal(max_v + base1);
    if (start_v == -1)
        for (int i = base1; i < max_v + base1; i++) max_dist[i] = 0, cal[i] = 1;
    else
        max_dist[start_v] = 0, cal[start_v] = 1;
 
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) //start_v로 부터의 유효한 정점에 대해서만 max 갱신
                max_dist[adj.v] = max(max_dist[adj.v], adj.w + n.w), cal[adj.v]=1;
            in_edge[adj.v]--;
            enqueue({ adj.v, max_dist[adj.v] });
        }
    }
    return max_dist;
}
 
int32_t main()
{
    int n, m; cin >> n >> m;
    vvn adj_list(n + 1), adj_list2(n + 1);
    vi in(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj_list[u].push_back({ v, w }); in[v]++;
        adj_list2[v].push_back({ u, w });
    }
    int s, e; cin >> s >> e;
    vi md = longest(n, s, adj_list, in, true);
    cout << md[e] << endl;
 
    //이제 거꾸로 가면서 간선 개수 카운팅
    set<pair<intint>> edges;
    queue<node> q; q.push({ e, md[e] });
    vi visited(10001);
    while (q.size()) {
        node n = q.front(); q.pop();
        if (visited[n.v]) continue;
        visited[n.v] = 1;
        if (n.v == s) break;
        for (node adj : adj_list2[n.v]) {
            if (n.w - adj.w == max_dist[adj.v])
                q.push({ adj.v, n.w - adj.w }),
                edges.insert({ min(n.v,adj.v), max(n.v,adj.v) });
        }
    }
    cout << edges.size() << endl;
    return 0;
}
cs


위의 코드를 한층 더 업그레이드(?)해서.. 간선가중치 뿐 아니라 정점가중치도 고려하고, 경로도 구해주는 버전을 만들었다.

이 문제의 답안이기도 하다. 단, 문제특성상 아래코드는 간선가중치는 작을수록 좋고, 정점코스트는 클수록 좋음에 주의

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
 
const int INF = (int)1e9;
struct node { int v, w; };
using vi = vector<int>;
using vvn = vector<vector<node>>;
//간선가중치(adj_list)뿐 아니라 정점가중치(cost)도 같이 고려.
//모든 노드로의 longest 한번에 구하기, 최장거리와 경로도 같이 리턴해준다.
struct result { vi max_dist; int max_value; vi path; };
result longest(int max_v,int start_v,vvn& adj_list,vi& in_edge,vi& cost,int base1) {
    vi visit(max_v + base1), max_dist(max_v + base1, -INF), from(max_v + base1, INF);
    queue<node> q;
    function<bool(node)> enqueue = [&](node n)->bool {
        if (in_edge[n.v] != 0return false;
        q.push(n);
        return true;
    };
 
    //start_v와 무관해도 indgree=0인 정점은 모두 넣어야, 위상정렬이 정상 진행됨
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
    vi cal(max_v + base1);
    if (start_v == -1
        for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i], cal[i] = 1
    else 
        max_dist[start_v] = cost[start_v], cal[start_v] = 1
 
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) //start_v로 부터의 유효한 정점에 대해서만 max 갱신
                max_dist[adj.v] = max(max_dist[adj.v], cost[adj.v] - adj.w + n.w),
                cal[adj.v] = 1;
            in_edge[adj.v]--;
            if (enqueue({ adj.v, max_dist[adj.v] })) from[adj.v] = n.v;
        }
    }
 
    //아래는 좀 비효율적, 위의 복잡도를 높이지 않게 하기위해 걍 놔둠
    int ra = -INF, rb = -1;
    for (int i = base1; i < max_v + base1; i++)
        if (max_dist[i] > ra) ra = max_dist[i], rb = i;
    deque<int> s;
    int ix = rb;
    while (ix != INF)s.push_front(ix), ix = from[ix];
    return { max_dist, ra, vi(s.begin(), s.end()) };
}
 
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T; while (T--) {
        int N, E; cin >> N >> E;
        vi cost(N + 1); for (int i = 1; i <= N; i++) { cin >> cost[i]; }
        vector<vector<node>> adj_list(N + 1);
        vi in(N + 1);
        for (int i = 0; i < E; i++) {
            int u, v, w; cin >> u >> v >> w;
            adj_list[u].push_back({ v, w }); in[v]++;
        }
        result r = longest(N, 1, adj_list, in, cost, true);
        cout << r.max_value << ' ' << (int)(r.path).size() << '\n';;
        for (auto a : r.path) cout << a << ' ';
        cout << endl;
    }
    return 0;
}
cs



반응형

just store Lunlun numbers in an array.좋은 문제를 발견하면, 그 문제의 뽕을 뽑아먹는(충분히 검토하는) 코뽕시간입니다 ㅎ


오늘의 코뽕문제는 AtCoder Beginner Contest 161 - D Lunlun Number가 되겠습니다.

이 문제는 설명이 단순하고 쉽기 때문에 나중에 다시 문제를 recall하기도 좋고 풀이도 다양해서 코뽕에 아주 적합한 문제가 되겠습니다.

참고로 이 Lunlun number는 OEIS에 등록되어 있습니다.


이문제는 대략 살펴보아도 


브루트포스, 백트래킹, 이진탐색, Queue 등을 이용해서 풀 수 있는걸로 보입니다.


브루트 포스를 이용한 방법

먼저 브루트포스를 이용한 방법은, 단순히 1씩 증가시키면서 lunlun 넘버인지 보는코드에다가 일정부분을 스킵할 수 있는 코드를 삽입하는 간단한 방법입니다. 샘플코드는 다음과 같습니다.

예들들어 현재 숫자가 243일때 2가 violation이므로 둘째자리 숫자인 4가 9가 될때까지 50을 더해서 293까지 skip한다는 idea. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
ll lun[100001];
int check_lunlun(ll i) {
    int a = -1;
    int jari = 1;
    while (i) {
        int ii = i % 10;
        if (a == -1) a = ii;
        else if (abs(a - ii) > 1) {
            if (a > ii && a < 9)
                return (jari / 10* (10 - a - 1);
            else return 1;
        }
        i /= 10; jari *= 10, a = ii;
    }
    return 0;
}
int main() {
    int K; scanf("%d"&K);
    int k = 1;
    for (ll i = 1; k <= K; i++) {
        ll skip = check_lunlun(i);
        if (skip == 0) lun[k++= i;
        else i += skip - 1;
    }
    printf("%lld\n", lun[K]);
    return 0;
}
cs

이정도 아이디어만 가지고도 AC를 받기에는 충분(대략 700ms정도 걸림)

다른 아이디어도 적용하면 좀 더 스킵할수도 있을것임


아래는 다른사람들 방법

just store Lunlun numbers in an array.

근데 이건 원리상 아래 BFS랑 동일한거 같다.


백트래킹을 이용한 방법

678이라는 임의의 Lunlun넘버를 생각해 봤을때, 다음처럼 3가지 경우로 갈 수 있다고 생각하고, DFS를 돌리는 아이디어.


이건 실전에서 구현하기도 좋아보인다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
map<ll, int> m;
void dfs(ll i) {
    m[i] = 1
    if (i > 3234566667ll) return;
    int ld = i % 10;
    if(ld+1<=9) dfs(i * 10 + ld + 1);
    dfs(i * 10 + ld);
    if(ld-1>=0)dfs(i * 10 + ld - 1);
}
int main()
{
    for (int i = 1; i < 10; i++) dfs(i);
    int k; cin >> k;
    int ix = 1;
    for (auto a : m) {
        if (ix++ == k) cout << a.first << endl;
    }
    return 0;
}
cs

특별히 백트래킹이랄것도 없고.. 그냥 최대숫자보다 커지면 return하는게 다인데.. 저 최대숫자를 모르면 좀 애매하다는게 문제라면 문제.. DFS특성상 11111111111111 이런숫자를 먼저 최대자리수까지 파는 경향이 있기 때문에 더욱그렇다.


BFS를 이용한 방법

에디토리얼에서도 이걸 정해로 주장하고 있다.

뭐 기본적으로 DFS와 동일한 아이디어 인데, 최대숫자를 guessing할 필요가 없고 그냥, 값이 채워진게 10만번째이면 바로 break하면 되기 때문에 좀 더 안전성이 있다. 부채모양으로 퍼져나가니 찾자마자 최단거리가 되는 원리랑 조금 비슷한게 담긴거 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
map<ll, int> m;
int main()
{
    int k; cin >> k;
    queue<ll> q;
    for (int i = 1; i < 10; i++) q.push(i);
    while (q.size()) {
        ll n = q.front(); q.pop();
        m[n] = 1;
        if (m.size() > 100000break;
        if(n%10!=0) q.push(n * 10 + n % 10 - 1);
        q.push(n * 10 + n % 10);
        if(n%10!=9) q.push(n * 10 + n % 10 + 1);
    }
    int ix = 1;
    for (auto a : m) {
        if (ix++ == k) cout << a.first << endl;
    }
    return 0;
}
cs

실전에서는 이코드처럼 정확히 10만에서 break하면 좀 위험할수도 있으니, 좀더 버퍼를 주는게 좋겠지만, 어쨌든 DFS보다는 나은 어프로치인듯하다.

덕북에 실행속도와 메모리 사용량에 있어서도 3배정도는 이득이 있는듯?


아래는 다른사람들 BFS구현

https://atcoder.jp/contests/abc161/submissions/11513177

https://atcoder.jp/contests/abc161/submissions/11518213

이진탐색을 이용한 방법

이진탐색+DigitDP 솔루션 : https://atcoder.jp/contests/abc161/submissions/11532810

이건 오버 엔지니어링 같아서 보기가 좀 싫어지네 ㅎ 나중에 보자.


반응형

'Programming > Problem Solving' 카테고리의 다른 글

BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (0) 2020.04.09
Visual Studio Code  (0) 2020.04.03
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
C++ bigint class  (0) 2020.03.30

맥에서 코딩하기 위해, Visual Studio Code를 세팅해보았다.


https://ldgeao99.tistory.com/203 이 링크가 가장 도움이 됐지만 일부 세팅은 다시 해줘야 했다(디버깅용 -g 옵션, a.out 등)


tasks.jon과 launch.json이 필요한데.. 현재 내 설정 공개한다.


tasks.jon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
{
    "version": "2.0.0",
    "runner": "terminal",
    "type": "shell",
    "echoCommand": true,
    "presentation" : { "reveal": "always" },
    "tasks": [
          //C++ 컴파일
          {
            "label": "C++빌드하자",
            "command": "g++",
            "args": [
                "-g",
                "-std=c++11",
                "${file}",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}"
            ],
            "group": "build",
 
            //컴파일시 에러를 편집기에 반영
            //참고:   https://code.visualstudio.com/docs/editor/tasks#_defining-a-problem-matcher
 
            "problemMatcher": {
                "fileLocation": [
                    "relative",
                    "${workspaceRoot}"
                ],
                "pattern": {
                    // The regular expression. 
                   //Example to match: helloWorld.c:5:3: warning: implicit declaration of function 'prinft'
                    "regexp": "^(.*):(\\d+):(\\d+):\\s+(warning error):\\s+(.*)$",
                    "file": 1,
                    "line": 2,
                    "column": 3,
                    "severity": 4,
                    "message": 5
                }
            }
        },
        {
 
            "label": "실행",
            "command": "cd ${fileDirname} && ./${fileBasenameNoExtension}",
            "group": "test"
        }
    ]
}
cs


launch.jon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
{
    // IntelliSense를 사용하여 가능한 특성에 대해 알아보세요.
    // 기존 특성에 대한 설명을 보려면 가리킵니다.
    // 자세한 내용을 보려면 https://go.microsoft.com/fwlink/?linkid=830387을(를) 방문하세요.
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(lldb) 연결",
            "type": "cppdbg",
            "request": "attach",
            "program": "${workspaceFolder}/a.out",
            "processId": "${command:pickProcess}",
            "MIMode": "lldb"
        },
        {
            "name": "(lldb) 시작",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}/a",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "lldb"
        }
    ]
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
C++ bigint class  (0) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15

탑코더할때는 moj를 많이 썼는데, 자동으로 내 템플릿코드 가져오고, testcase 빌드할 수 있게 해주는등 온라인저지 이용시 시간단축에 도움이 된다.


코드포스로 옮기면서 비슷한걸 찾아봤는데 VsCaide라는걸 찾았다.


그냥 visual studio 2019에서 확장 > 확장관리 들어가서 vscaide로 검색하고 설치하면 된다 (간단)



반응형

'Programming > Problem Solving' 카테고리의 다른 글

[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
Visual Studio Code  (0) 2020.04.03
C++ bigint class  (0) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01

이 문제에서 연습할 수 있다.

아래 소스는 위 문제의 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main() {
    int S = 0;
    int M; scanf("%d"&M); while (M--) {
        char a[10]; int b; scanf("%s", a);
 
        string s = a;
        if (s == "add"scanf("%d"&b), S |= (1 << (b - 1));
        if (s == "check"scanf("%d"&b), printf("%d\n", S & (1 << (b - 1)) ? 1 : 0);
        if (s == "remove"scanf("%d"&b), S &= ~(1 << (b - 1));
        if (s == "toggle"scanf("%d"&b), S ^= (1 << (b - 1));
        if (s == "all") S = 0 - 1;
        if (s == "empty") S = 0;
    }
    return 0;
}
cs

조금 까리하건 remove와 toggle인데 생각해내기 어렵진 않다.



반응형

여기나온게 지금까지 내가 알기로는 가장 좋다.

내 github에도 저장해두었다.

아래는 bigint를 사용한 A+B샘플(백준15740문제의 답안이기도 하다)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
#include <bits/stdc++.h>
using namespace std;
/*
  ######################################################################
  #######################   THE   BIG   INT   ##########################
*/
const int base = 1000000000;
const int base_digits = 9;
struct bigint {
    vector<int> a;
    int sign;
    /*<arpa>*/
    int size() {
        if (a.empty())return 0;
        int ans = (a.size() - 1* base_digits;
        int ca = a.back();
        while (ca)
            ans++, ca /= 10;
        return ans;
    }
    bigint operator ^(const bigint& v) {
        bigint ans = 1, a = *this, b = v;
        while (!b.isZero()) {
            if (b % 2)
                ans *= a;
            a *= a, b /= 2;
        }
        return ans;
    }
    string to_string() {
        stringstream ss;
        ss << *this;
        string s;
        ss >> s;
        return s;
    }
    int sumof() {
        string s = to_string();
        int ans = 0;
        for (auto c : s)  ans += c - '0';
        return ans;
    }
    /*</arpa>*/
    bigint() :
        sign(1) {
    }
 
    bigint(long long v) {
        *this = v;
    }
 
    bigint(const string& s) {
        read(s);
    }
 
    void operator=(const bigint& v) {
        sign = v.sign;
        a = v.a;
    }
 
    void operator=(long long v) {
        sign = 1;
        a.clear();
        if (v < 0)
            sign = -1, v = -v;
        for (; v > 0; v = v / base)
            a.push_back(v % base);
    }
 
    bigint operator+(const bigint& v) const {
        if (sign == v.sign) {
            bigint res = v;
 
            for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i) {
                if (i == (int)res.a.size())
                    res.a.push_back(0);
                res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
                carry = res.a[i] >= base;
                if (carry)
                    res.a[i] -= base;
            }
            return res;
        }
        return *this - (-v);
    }
 
    bigint operator-(const bigint& v) const {
        if (sign == v.sign) {
            if (abs() >= v.abs()) {
                bigint res = *this;
                for (int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i) {
                    res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
                    carry = res.a[i] < 0;
                    if (carry)
                        res.a[i] += base;
                }
                res.trim();
                return res;
            }
            return -(v - *this);
        }
        return *this + (-v);
    }
 
    void operator*=(int v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
            if (i == (int)a.size())
                a.push_back(0);
            long long cur = a[i] * (long long)v + carry;
            carry = (int)(cur / base);
            a[i] = (int)(cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }
 
    bigint operator*(int v) const {
        bigint res = *this;
        res *= v;
        return res;
    }
 
    void operator*=(long long v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
            if (i == (int)a.size())
                a.push_back(0);
            long long cur = a[i] * (long long)v + carry;
            carry = (int)(cur / base);
            a[i] = (int)(cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }
 
    bigint operator*(long long v) const {
        bigint res = *this;
        res *= v;
        return res;
    }
 
    friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1) {
        int norm = base / (b1.a.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.a.resize(a.a.size());
 
        for (int i = a.a.size() - 1; i >= 0; i--) {
            r *= base;
            r += a.a[i];
            int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
            int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
            int d = ((long long)base * s1 + s2) / b.a.back();
            r -= b * d;
            while (r < 0)
                r += b, --d;
            q.a[i] = d;
        }
 
        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return make_pair(q, r / norm);
    }
 
    bigint operator/(const bigint& v) const {
        return divmod(*this, v).first;
    }
 
    bigint operator%(const bigint& v) const {
        return divmod(*this, v).second;
    }
 
    void operator/=(int v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = (int)a.size() - 1, rem = 0; i >= 0--i) {
            long long cur = a[i] + rem * (long long)base;
            a[i] = (int)(cur / v);
            rem = (int)(cur % v);
        }
        trim();
    }
 
    bigint operator/(int v) const {
        bigint res = *this;
        res /= v;
        return res;
    }
 
    int operator%(int v) const {
        if (v < 0)
            v = -v;
        int m = 0;
        for (int i = a.size() - 1; i >= 0--i)
            m = (a[i] + m * (long long)base) % v;
        return m * sign;
    }
 
    void operator+=(const bigint& v) {
        *this = *this + v;
    }
    void operator-=(const bigint& v) {
        *this = *this - v;
    }
    void operator*=(const bigint& v) {
        *this = *this * v;
    }
    void operator/=(const bigint& v) {
        *this = *this / v;
    }
 
    bool operator<(const bigint& v) const {
        if (sign != v.sign)
            return sign < v.sign;
        if (a.size() != v.a.size())
            return a.size() * sign < v.a.size()* v.sign;
        for (int i = a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }
 
    bool operator>(const bigint& v) const {
        return v < *this;
    }
    bool operator<=(const bigint& v) const {
        return !(v < *this);
    }
    bool operator>=(const bigint& v) const {
        return !(*this < v);
    }
    bool operator==(const bigint& v) const {
        return !(*this < v) && !(v < *this);
    }
    bool operator!=(const bigint& v) const {
        return *this < v || v < *this;
    }
 
    void trim() {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            sign = 1;
    }
 
    bool isZero() const {
        return a.empty() || (a.size() == 1 && !a[0]);
    }
 
    bigint operator-() const {
        bigint res = *this;
        res.sign = -sign;
        return res;
    }
 
    bigint abs() const {
        bigint res = *this;
        res.sign *= res.sign;
        return res;
    }
 
    long long longValue() const {
        long long res = 0;
        for (int i = a.size() - 1; i >= 0; i--)
            res = res * base + a[i];
        return res * sign;
    }
 
    friend bigint gcd(const bigint& a, const bigint& b) {
        return b.isZero() ? a : gcd(b, a % b);
    }
    friend bigint lcm(const bigint& a, const bigint& b) {
        return a / gcd(a, b) * b;
    }
 
    void read(const string& s) {
        sign = 1;
        a.clear();
        int pos = 0;
        while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
            if (s[pos] == '-')
                sign = -sign;
            ++pos;
        }
        for (int i = s.size() - 1; i >= pos; i -= base_digits) {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            a.push_back(x);
        }
        trim();
    }
 
    friend istream& operator>>(istream& stream, bigint& v) {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }
 
    friend ostream& operator<<(ostream& stream, const bigint& v) {
        if (v.sign == -1)
            stream << '-';
        stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int)v.a.size() - 2; i >= 0--i)
            stream << setw(base_digits) << setfill('0'<< v.a[i];
        return stream;
    }
 
    static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits) {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0= 1;
        for (int i = 1; i < (int)p.size(); i++)
            p[i] = p[i - 1* 10;
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int i = 0; i < (int)a.size(); i++) {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits) {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int)cur);
        while (!res.empty() && !res.back())
            res.pop_back();
        return res;
    }
 
    typedef vector<long long> vll;
 
    static vll karatsubaMultiply(const vll& a, const vll& b) {
        int n = a.size();
        vll res(n + n);
        if (n <= 32) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }
 
        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());
 
        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);
 
        for (int i = 0; i < k; i++)
            a2[i] += a1[i];
        for (int i = 0; i < k; i++)
            b2[i] += b1[i];
 
        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < (int)a1b1.size(); i++)
            r[i] -= a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            r[i] -= a2b2[i];
 
        for (int i = 0; i < (int)r.size(); i++)
            res[i + k] += r[i];
        for (int i = 0; i < (int)a1b1.size(); i++)
            res[i] += a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            res[i + n] += a2b2[i];
        return res;
    }
 
    bigint operator*(const bigint& v) const {
        vector<int> a6 = convert_base(this->a, base_digits, 6);
        vector<int> b6 = convert_base(v.a, base_digits, 6);
        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());
        while (a.size() < b.size())
            a.push_back(0);
        while (b.size() < a.size())
            b.push_back(0);
        while (a.size() & (a.size() - 1))
            a.push_back(0), b.push_back(0);
        vll c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for (int i = 0, carry = 0; i < (int)c.size(); i++) {
            long long cur = c[i] + carry;
            res.a.push_back((int)(cur % 1000000));
            carry = (int)(cur / 1000000);
        }
        res.a = convert_base(res.a, 6, base_digits);
        res.trim();
        return res;
    }
};
/*
  #######################   THE   BIG   INT   ##########################
  ######################################################################
*/
 
 
 
 
string a, b;
int main(void)
{
    cin >> a >> b;
    bigint A(a), B(b), C;
    C = A + B;
    cout << C.to_string() << endl;
    return 0;
}
 
 
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

Visual Studio Code  (0) 2020.04.03
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21

CentOS 기준..


/etc/ntp.conf 추가 

server time1.sevity.com

server time2.sevity.com


서비스 등록 확인

chkconfig --list | grep ntpd


재시작

/etc/init.d/ntpd restart


확인

ntpq -p 

여기서 앞에 *붙으면 싱크받고 있음을 의미


아래는 CentOS 7기준

firewall-cmd --add-service=ntp --permanent

방화벽을 다시 로드합니다.

firewall-cmd --reload


서비스 시작

ntp 서비스를 시작합니다.

systemctl start ntpd


시스템 재부팅 후에도 자동으로 시작할 수 있도록 합니다.

systemctl enable ntpd



반응형

'Programming > Linux' 카테고리의 다른 글

vim  (0) 2020.09.20
리눅스 퍼미션 개념(파일 권한 관련)  (0) 2020.04.10
supervisor  (0) 2020.03.18
ssh 자동로그인(ssh-keygen)  (0) 2020.03.10
scp관련  (0) 2019.12.05

DFS를 이용한 방법

DFS를 사용한 사이클 검증법은 보통 $O(V)$로 이야기 되는 것 같다. 만약 간선이 많다고 하더라도 V번 안에 back edge가 발견돼서 끝나서 그런듯. (끝까지 사이클이 없는 경우에 최대 V정점, 최대 V간선을 방문하니 2V라서 $O(V)$가 맞긴한듯)

 

back edge를 발견하면 사이클이 있다고 판단하는건데, 순회와 백엣지 개념은 여기가 설명 잘되어 있다.

 

코드는 여기가 좋은 것 같긴한데.. 문제는 딱맞는 샘플문제가 없어서 해보지 못했다

 

여기에 샘플문제가 있고 제출도 가능한것 같아서 해보는 중.

 

DFS로 직접 한 번 구현해보니까, visit배열만 있어도 판단이 되는데, visit를 1로했다 0으로 했다하는 테크닉이 필요했다.아래 cache는 나중에 추가했는데.. 저거 없어도 위에 샘플이 돌긴하는데 TLE가 나길래 추가했고, 추가한 후에 AC떴다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
 
 
int V, E, u, v, w, in[101][101], visited[101], cache[101];
 
int DFS_has_cycle(int cur_v) {
    if (cache[cur_v] != INT_MAX) return cache[cur_v];
    visited[cur_v] = 1;
    for (int i = 0; i < V; i++) {
        if (in[cur_v][i]){
            if (visited[i]) return cache[cur_v] = 1;  //back-edge발견, 사이클!
            if (DFS_has_cycle(i)) return cache[cur_v] = 1;
        }
    }
    visited[cur_v] = 0;  // 이부분이 중요(back track한다음에는 0으로 만들어줘야 트리구조로 들어간다.)
    return cache[cur_v] = 0;
}
 
int main()
{
    const int INF = INT_MAX / 4;
    scanf("%d%d"&V, &E);
    fill(&in[0][0], &in[V][V], 0);
    for (int i = 0; i < E; i++) {
        scanf("%d%d"&u, &v);
        in[u][v] = 1;
    }
    
    bool ans = false;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < 101; j++)visited[j]=0, cache[j]=INT_MAX;
        if (DFS_has_cycle(i)) { ans = truebreak; }
    }
 
    printf("%d\n", ans ? 1 : 0);
    return 0;
}
 
cs

근데, 내가 다른사람하고 같은 방식으로 짰는지는 잘 모르겠다;; 

뭔가 여러가지 방식이 있는 느낌이라 좀 헷갈린다.

 

나중에 다른 문제를 풀다가 위의 구현을 썼더니 TLE가 나서 아래 구현으로 바꿨더니 통과했다; 아직 위의 구현에 어떤 문제땜에 느린지 파악은 못함

음 파악해 봤는데.. 위에서 매번 visited, cache 초기화 해주는게 O(N)이다 보니 모든 노드에 대해서 DFS_has_cycle()부르면 O(N^2)이상이 될 수 있는게 문제였다 ㄷ. 아래 소스는 cache는 아예 안쓰고, visited도 한번만 초기화해주면 되다보니 빨랐던것

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
 
bool has_cycle(int max_v, int cur_v, vvi& adj_list, bool base1 = false) {
    if (base1) max_v++;
    static vi visited; if (visited.size() != max_v)visited.resize(max_v, 0);
    function<bool(int)> dfs = [&](int cur_v) -> bool {
        if (visited[cur_v]) {
            if (visited[cur_v] == -1return true;
            return false;
        }
        visited[cur_v] = -1;
        for (int adj : adj_list[cur_v]) {
            if (dfs(adj)) {
                return true;
            }
        }
        visited[cur_v] = 1;
        return false;
    };
    return dfs(cur_v);
}
 
int main()
{
    int N, M; cin >> N >> M;
    vector<vector<int>> adj_list(N);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        adj_list[u].push_back(v);
    }
 
    bool ans = false;
    for (int i = 0; i < N; i++) {
        if (has_cycle(N, i, adj_list)) { ans = truebreak; }
    }
 
    printf("%d\n", ans ? 1 : 0);
    return 0;
}
cs

 

 

그리고 이게또 direct냐 undirect에 따라서도 다른거 같다.(위는 direct 버전)

 

undirect 버전

undirect는 양방향으로 간선을 처리해준다음에, 트리 순회처럼 parent-child관계로 탐색해 나가고, 

바로전(justbefore)으로 돌아가는 간선은 무시해주는 식으로 처리하면 된다.

이 문제를 통해서 볼 수 있고, 완전한 코드는 아니지만, 아래 코드 참조하자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using vi = vector<int>;
using vvi = vector<vi>;
bool has_cycle(int max_v, int cur_v, vvi& adj_list, bool base1 = false) {
    if (base1) max_v++;
    static vi visited; if (visited.size() != max_v)visited.resize(max_v, 0);
    function<bool(intint)> DFS = [&](int curr, int justbefore) -> bool {
        visited[curr] = true;
 
        for (auto child : adj_list[curr]) {
            if (child == justbefore) continue;
            // cycle 이 생기면
            if (visited[child]) return false;
            if (DFS(child, curr) == falsereturn false;
        }
        return true;
    };
    return DFS(cur_v, -1);
}
cs

 

 

그리고 사이클 존재 여부만 판단하느냐, 최소사이클수 같은걸 판단하느냐도 다른듯

최소사이클의 경우는 DFS만으로 커팅하면서 빠르게 판단하기 힘든게 아닌가 생각중

(최소 사이클 나오면 Floyd-Warshall Algorithm 현재 내가아는한에서는 답이다)

 

 

유니온파인드를 통한 디텍션

undirected의 경우 이 문제의 경우처럼 유니온파인드로도 사이클 디텍션을 할 수 있다.

좀 더 구체적으로는 새로운 간선을 union할 때, 양쪽 정점이 이미 같은 parent를 가지고 있으면, 사이클로 판정가능하다. (중복 간선은 없다는 가정하에, 이미 연결되어 있는데 부가적인 연결이 생기는거라)

간선이 추가되면서 특정 간선이 추가될때 사이클이 완성됨을 판정할때는 dfs보다 유리한 것 같다.

다음은 내 구현이다. 위 문제의 답안이기도 하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct union_find {
    vector<int> p, r;
    union_find(int n) {
        p.resize(n + 1), r.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            p[i] = i;
        }
    }
    int find(int x) {
        if (p[x] == x) return x;
        else return p[x] = find(p[x]);
    }
 
    void uni(int a, int b) {
        a = find(a);
        b = find(b);
        if (r[a] < r[b]) p[b] = a;
        else p[a] = b;
        if (r[a] == r[b]) r[a]++;
    }
};
int32_t main()
{
    int n, m; scanf("%d%d"&n, &m);
    union_find uf(n);
    REP(i, m) {
        int u, v; scanf("%d%d"&u, &v);
        if (uf.find(u) == uf.find(v)) {
            printf("%d\n", i + 1);
            return 0;
        }
        else {
            uf.uni(u, v);
        }
    }
    printf("0\n");
    return 0;
}
 
cs

 

 

트리 디텍션과도 일맥상통.

반응형

+ Recent posts