BOJ : https://www.acmicpc.net/problem/10451

GitHub : https://github.com/junho0956/Algorithm/blob/master/10451/10451/%EC%86%8C%EC%8A%A4.cpp

 

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
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v[1001];
bool visit[1001];
int T, N, vertex, check;
 
void dfs(int vertex) {
    if (visit[vertex]) return;
    visit[vertex] = 1;
    check--;
 
    dfs(v[vertex][0]);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 1; i <= N; i++) {
            cin >> vertex;
            v[i].push_back(vertex);
        }
 
        check = N;
        int cnt = 0, start;
        while (check) {
            cnt++;
            for (int i = 1; i <= N; i++) {
                if (!visit[i]) {
                    start = i;
                    break;
                }
            }
            dfs(start);
        }
 
        cout << cnt << '\n';
        for (int i = 1; i <= N; i++) {
            visit[i] = 0;
            v[i].clear();
        }
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2667번 단지번호붙이기  (0) 2020.01.14
BOJ 9466번 텀 프로젝트  (0) 2020.01.14
BOJ 2331번 반복 수열  (0) 2020.01.14
BOJ 1707번 이분 그래프  (0) 2020.01.13
BOJ 11724번 연결 요소의 개수  (0) 2020.01.13

BOJ : https://www.acmicpc.net/problem/2331

GitHub : https://github.com/junho0956/Algorithm/blob/master/2331/2331/%EC%86%8C%EC%8A%A4.cpp

 

반복수열의 범위를 먼저 확인해보는게 중요하다.

한자리 숫자가 가질 수 있는 값 중 가장 큰 값은 9이고 9 의 5 제곱은 5만쯤 된다.

D[1] 이 최대 9999 이니 *4 를 하면 20만이고 (사실 정확히 계산해보면 236196)

길이가 어떻게 길어질지 계산해보기 귀찮아서 어림잡아 100만을 줬는데 반복 수열을 확인하는데는 

충분한 범위일 것 같다.

 

이후부터는 문제가 요구하는대로 수열을 찾아서 첫 위치에 대한 카운트를 해주면 된다.

 

더보기
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
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v;
bool arr[1000001], check = 1;
 
int main() {
    int A, P, index = 0;
    cin >> A >> P;
    v.push_back(A);
    arr[A] = 1;
 
    int total;
    while (check) {
        total = 0;
        int temp = v[index];
        while (temp) {
            int num = temp % 10;
            int cnt = P;
            int test = 1;
            while (cnt--) test *= num;
            total += test;
            temp /= 10;
        }
        if (arr[total]) {
            check = 0;
        }
        else arr[total] = 1, v.push_back(total), index++;
    }
 
    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == total) break;
        cnt++;
    }
 
    cout << cnt;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 9466번 텀 프로젝트  (0) 2020.01.14
BOJ 10451번 순열 사이클  (0) 2020.01.14
BOJ 1707번 이분 그래프  (0) 2020.01.13
BOJ 11724번 연결 요소의 개수  (0) 2020.01.13
BOJ 1260번 DFS와 BFS  (0) 2020.01.13

BOJ : https://www.acmicpc.net/problem/1707

GitHub : https://github.com/junho0956/Algorithm/blob/master/1707/1707/%EC%86%8C%EC%8A%A4.cpp

 

이분 그래프는 그래프를 정확히 2종류의 정점 집합으로 나눌 수 있는가에 대한 문제이다.

집합을 나누는 기준은 임의의 정점과 연결된 정점이 서로 다른 관계임을 표현하면 된다.

** 트리가 아닌 그래프를 표현할 때는 방향이 없으므로 서로 이어주도록 하자.. 이거 때문에 처음에 틀렸다 ㅜㅜ**

** 이분 그래프는 모든 정점이 반드시 연결되어 있지 않을 수도 있다 ==> 연결요소가 몆개인지 알 수 없다 **

** 매 테스트케이스마다 초기화를 잘해줘야 한다 **

 

임의의 첫 출발점을 0 이라는 관계를 주었으면 이 정점과 연결된 모든 정점은 반드시

0이 아닌 다른 관계(ex:1) 를 주어야 한다.

이후 임의의 정점에 연결된 정점을 확인할 때 자신과 같은 관계가 있다면 이분 그래프가 될 수 없다.

 

더보기
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
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
 
queue<int> q;
vector<int> v[20001];
bool graph[20001];
bool visit[20001];
int K, vertex, edge, s, e;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> K;
    while (K--) {
        cin >> vertex >> edge;
 
        memset(graph, -1, sizeof(graph));
        memset(visit, 0, sizeof(visit));
        for (int i = 1; i <= vertex; i++) v[i].clear();
 
        for (int i = 0; i < edge; i++) {
            cin >> s >> e;
            v[s].push_back(e);
            v[e].push_back(s);
        }
 
        bool check = true;
        
        int cnt = vertex, start;
        while (cnt) {
            for (int i = 1; i <= vertex; i++) {
                if (!visit[i]) {
                    start = i;
                    break;
                }
            }
            q.push(start);
            graph[start] = 0;
 
            while (!q.empty()) {
                int cur = q.front();
                int now = graph[cur];
                q.pop();
 
                if (visit[cur]) continue;
                visit[cur] = 1;
                cnt--;
 
                for (int i = 0; i < v[cur].size(); i++) {
                    if (graph[v[cur][i]] == now) {
                        check = false;
                        break;
                    }
                    if (!visit[v[cur][i]]) {
                        q.push(v[cur][i]);
                        if (now == 0) graph[v[cur][i]] = 1;
                        else graph[v[cur][i]] = 0;
                    }
                }
                if (!check) while (!q.empty()) q.pop();
            }
            if (!check) break;
        }
 
        if (check) cout << "YES\n";
        else cout << "NO\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10451번 순열 사이클  (0) 2020.01.14
BOJ 2331번 반복 수열  (0) 2020.01.14
BOJ 11724번 연결 요소의 개수  (0) 2020.01.13
BOJ 1260번 DFS와 BFS  (0) 2020.01.13
BOJ 2004번 조합 0의 개수  (0) 2020.01.13

BOJ : https://www.acmicpc.net/problem/11724

GitHub : https://github.com/junho0956/Algorithm/blob/master/11724/11724/%EC%86%8C%EC%8A%A4.cpp

 

연결요소의 개수를 파악하라는 것은

전체 그래프의 개수를 구하라는 것이다.

모든 정점이 다 연결된게 아닐수도 있으니 끊어져있는 경우 개수를 증가시키라는 말이다.

코드포스할때 하모니 그래프 문제를 풀었던 기억이 있는데

이 문제가 기본 베이스가 되지 않을까 생각한다.

 

더보기
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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int N, M, s, e;
vector<int> v[1001];
bool visit[1001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> s >> e;
        v[s].push_back(e);
        v[e].push_back(s);
    }
 
    int cnt = N, start, sum = 0;
    queue<int> q;
    
    while (cnt) {
        sum++;
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                start = i;
                break;
            }
        }
        q.push(start);
        while (!q.empty()) {
            int num = q.front();
            q.pop();
 
            if (visit[num]) continue;
            visit[num] = 1;
            cnt--;
 
            for (int i = 0; i < v[num].size(); i++) {
                if (visit[v[num][i]] == 0) q.push(v[num][i]);
            }
        }
    }
 
    cout << sum;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2331번 반복 수열  (0) 2020.01.14
BOJ 1707번 이분 그래프  (0) 2020.01.13
BOJ 1260번 DFS와 BFS  (0) 2020.01.13
BOJ 2004번 조합 0의 개수  (0) 2020.01.13
BOJ 1676번 팩토리얼 0의 개수  (0) 2020.01.13

+ Recent posts

티스토리툴바