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

 

20040번: 사이클 게임

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한

www.acmicpc.net

코테를 자바로 해야하기 때문에 오랜만에 자바로 리뷰를 합니다...

오랜만에 자바로 알고리즘 하니까 어색하네요

 

기본적인 union-find를 활용해볼 수 있는 문제입니다.

 

u와 v 노드를 연결 할 때 사이클이 생기는 경우는 u의 루트와 v의 루트가 같을 때입니다.

따라서 union-find 과정 중에 u의 루트와 v의 루트가 같은지 확인하여 같으면 true, 다르면 false를 리턴해주었고,

 

맨 처음 true를 받아온 경우에만 ans에 갱신 해주었습니다.

(사이클이 생기지 않는 경우도 있기 때문에 생각을 해주어야합니다.)

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int parent[] = new int[500001];
    static int N, M, ans;
 
    static int find(int v) {
        if (parent[v] == v)
            return v;
        return parent[v] = find(parent[v]);
    }
 
    static boolean union(int x, int y) {
        int a = find(x);
        int b = find(y);
 
        if (a == b)
            return true;
        parent[b] = a;
        return false;
    }
 
    static void init() {
        for (int i = 0; i < N; i++)
            parent[i] = i;
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        init();
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            if (union(u, v) && ans == 0)
                ans = i;
        }
 
        System.out.println(ans);
    }
 
    public static void main(String[] args) throws Exception {
        input();
    }
}
 cs

'algorithm > Union-Find' 카테고리의 다른 글

boj 1043 거짓말  (0) 2021.04.05
boj 10775 공항  (0) 2021.03.17
boj 4195 친구 네트워크  (0) 2021.03.17
boj 1976 여행 가자  (0) 2021.03.17
boj 1717 집합의 표현  (0) 2021.02.06

www.acmicpc.net/problem/4195

 

4195번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

map을 이용하여 입력으로 이름이 들어오는 순서대로 인덱스를 부여합니다.

만약 이미 인덱스가 부여된 이름이라면 map에 저장된 인덱스를 가져옵니다.

 

이제 두 친구의 인덱스가 생겼으니 union-find로 둘을 이어줍니다.

이 때 Union 함수에서 a와 b가 다를때만 친구 네트워크 수를 b만큼 a에 더해줍니다.

 

 

 

[C++]

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
#include <iostream>
#include <string>
#include <map>
using namespace std;
 
map<string, int> m;
int parent[200001];
int friends[200001];
int N, idx;
 
int find(int v) {
    if (parent[v] == v) return v;
    return parent[v] = find(parent[v]);
}
 
void Union(int x, int y) {
    int a = find(x);
    int b = find(y);
 
    if (a != b) {
        parent[b] = a;
        friends[a] += friends[b];
    }
}
 
void input() {
    string str1, str2;
    int u, v;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> str1 >> str2;
 
        if (m.find(str1) == m.end()) {
            m.insert({ str1, idx });
            parent[idx] = idx;
            friends[idx] = 1;
            u = idx++;
        }
        else {
            u = m[str1];
        }
 
        if (m.find(str2) == m.end()) {
            m.insert({ str2, idx });
            parent[idx] = idx;
            friends[idx] = 1;
            v = idx++;
        }
        else {
            v = m[str2];
        }
 
        Union(u, v);
 
        cout << friends[find(u)] << '\n';
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        m.clear();
        idx = 0;
    }
 
    return 0;
}
 cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Map<String, Integer> m = new HashMap<>();
    static int parent[][] = new int[200001][2];
    static int N, idx = 1;
 
    static int find(int v) {
        if (parent[v][0] == v)
            return parent[v][0];
        return parent[v][0] = find(parent[v][0]);
 
    }
 
    static void union(int u, int v) {
        int a = find(u);
        int b = find(v);
 
        if (a != b) {
            parent[a][1] += parent[b][1];
            parent[b][0] = parent[a][0];
        }
        sb.append(parent[a][1]).append("\n");
    }
 
    static void init() {
        for (int i = 1; i <= N * 2; i++) {
            parent[i][0] = i;
            parent[i][1] = 1;
        }
    }
 
    static void input() throws Exception {
        String str1, str2;
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        init();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            str1 = st.nextToken();
            str2 = st.nextToken();
 
            if (m.containsKey(str1))
                u = m.get(str1);
            else {
                m.put(str1, idx);
                u = idx++;
            }
 
            if (m.containsKey(str2))
                v = m.get(str2);
            else {
                m.put(str2, idx);
                v = idx++;
            }
 
            if (v < u) {
                int tmp = u;
                u = v;
                v = tmp;
            }
 
            union(u, v);
        }
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
            m.clear();
            idx = 1;
        }
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > Union-Find' 카테고리의 다른 글

boj 20040 사이클 게임  (0) 2021.06.27
boj 1043 거짓말  (0) 2021.04.05
boj 10775 공항  (0) 2021.03.17
boj 1976 여행 가자  (0) 2021.03.17
boj 1717 집합의 표현  (0) 2021.02.06

www.acmicpc.net/problem/1976

 

1976번: 여행 가자

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인

www.acmicpc.net

두 가지 방법으로 해결하였습니다. 하나는 union-find를 이용한 방법, 하나는 dfs를 이용한 방법입니다.

 

먼저 union-find 방법입니다.

입력에서 인접한 도시의 정보가 주어집니다.

(i, j)가 0이면 인접X, 1이면 인접한 도시입니다.

1이 주어질때마다 union-find로 parent를 갱신해줍니다.

 

마지막으로 M개 도시의 parent가 모두 같으면 YES, 하나라도 다르면 NO입니다.

 

 

[Union-find]

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
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> travel;
int parent[201];
int N, M;
 
void init() {
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
}
 
int find(int v) {
    if (parent[v] == v) return v;
    return parent[v] = find(parent[v]);
}
 
void func() {
    int x = find(travel[0]);
    for (int i = 1; i < M; i++) {
        int y = find(travel[i]);
 
        if (x != y) {
            cout << "NO\n";
            return;
        }
    }
 
    cout << "YES\n";
}
 
void Union(int x, int y) {
    if (x > y) swap(x, y);
    
    int a = find(x);
    int b = find(y);
 
    parent[b] = a;
}
 
void input() {
    int k;
    cin >> N >> M;
    init();
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> k;
            if (k) {                
                Union(i, j);
            }
        }
    }
    
    for (int i = 0; i < M; i++) {
        cin >> k;
        travel.push_back(k);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

그 다음은 dfs를 이용한 방법입니다.

위와 마찬가지로 0이면 인접X, 1이면 인접한 정점이므로 벡터에 넣어줍니다.

그 다음 M개의 도시 중 첫번째 도시를 루트로 dfs를 돌려줍니다. (이 때 방문체크를 한 것을 이용합니다.)

 

마지막으로 dfs로 순회하면서 M개의 도시를 모두 방문하였는지 체크해줍니다.

하나라도 방문을 하지 않았으면 연결이 안되어있다는 말이므로 NO를 출력해줍니다.

M개의 도시를 모두 방문하였으면 YES를 출력합니다.

 

 

[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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> graph[201], travel;
bool visit[201];
int N, M;
 
void func() {
    for (int i = 0; i < M; i++) {
        int x = travel[i];
        if (visit[x]) continue;
 
        cout << "NO\n";
        return;
    }
 
    cout << "YES\n";
}
 
void dfs(int v) {
    visit[v] = true;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i];
 
        if (visit[next]) continue;
        dfs(next);
    }
}
 
void input() {
    int k;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> k;
            if (k) graph[i].push_back(j);
        }
    }
 
    for (int i = 0; i < M; i++) {
        cin >> k;
        travel.push_back(k);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    dfs(travel[0]);
    func();
 
    return 0;
}
 cs

'algorithm > Union-Find' 카테고리의 다른 글

boj 20040 사이클 게임  (0) 2021.06.27
boj 1043 거짓말  (0) 2021.04.05
boj 10775 공항  (0) 2021.03.17
boj 4195 친구 네트워크  (0) 2021.03.17
boj 1717 집합의 표현  (0) 2021.02.06

www.acmicpc.net/problem/1717

 

1717번: 집합의 표현

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는

www.acmicpc.net

union-find를 사용해볼 수 있는 문제입니다.

 

합집합 연산은 0 a b 형태로 주어지고, a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합친다는 의미입니다.

두 집합이 같은 집합인지 확인하는 연산은 1 a b 형태로 주어지고, a와 b가 같은 집합이면 YES, 아니면 NO를 출력하는 문제입니다.

 

저는 일단 parent배열에 집합의 루트를 자신으로 저장해놓고, union_find를 통해 a의 루트와 b의 루트를 찾아서

합치거나, 같은 집합인지 확인하였습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int parent[] = new int[1000001];
    static int N, M;
 
    static int find(int v) {
        if (parent[v] == v)
            return v;
        return parent[v] = find(parent[v]);
    }
 
    static void union(int u, int v) {
        int a = find(u);
        int b = find(v);
 
        if (parent[a] != parent[b])
            parent[b] = parent[a];
    }
 
    static void func() throws Exception {
        StringBuffer sb = new StringBuffer();
        int type, u, v;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            type = Integer.parseInt(st.nextToken());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            if (type == 0)
                union(Math.min(u, v), Math.max(u, v));
            else {
                if (find(u) == find(v))
                    sb.append("YES\n");
                else
                    sb.append("NO\n");
            }
        }
        
        System.out.print(sb.toString());
    }
 
    static void init() {
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        init();
        func();
    }
}
cs

'algorithm > Union-Find' 카테고리의 다른 글

boj 20040 사이클 게임  (0) 2021.06.27
boj 1043 거짓말  (0) 2021.04.05
boj 10775 공항  (0) 2021.03.17
boj 4195 친구 네트워크  (0) 2021.03.17
boj 1976 여행 가자  (0) 2021.03.17

+ Recent posts

티스토리툴바