티스토리 뷰

알고리즘/BOJ

[백준] 1412 일방통행

세진짱 2018. 6. 15. 22:50


X에서 출발해 X로 돌아올 수 있는지 없는지 판단하는 문제다

Cycle이 있으면 안되는 문제다.

하지만 양방향 간선끼리의 Cycle은 방향을 알아서 지정하면 되므로 

문제가 안된다..!


따라서 양방향인 간선들은 무시하고 단방향인 간선들로 그래프를 그린다

그리고 Cycle을 찾으면 된다!


Cycle을 찾는 함수를 사용해도 괜찮고 플로이드를 써도 괜찮다!


소스코드(Cycle detect)

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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, arr[111][111], check[111];
vector<vector<int>> Graph;
bool isCycle(int x) {
    if (check[x]) {
        if (check[x] == 1return false;
        return true;
    }
    check[x] = -1;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (isCycle(next)) return true;
    }
    check[x] = 1;
    return false;
}
int main() {
    scanf(" %d"&n);
    Graph.resize(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char a; scanf(" %1c"&a);
            if (a == 'Y') arr[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] && arr[j][i] && i != j || !arr[i][j]) continue;
            Graph[i].push_back(j);
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (check[i]) continue;
        if (isCycle(i)) {
            puts("NO"); return 0;
        }
    }
    puts("YES");
}
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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, arr[111][111], d[111][111];
 
int main() {
    scanf(" %d"&n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char a; scanf(" %1c"&a);
            if (a == 'Y') arr[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] && arr[j][i] && i !=|| !arr[i][j]) continue;
            d[i][j] = 1;
        }
    }
 
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][k] && d[k][j]) d[i][j] = 1;
            }
        }
    }
    for(int i=0;i<n;i++)
        if (d[i][i]) {
            puts("NO"); return 0;
        }
    puts("YES");
}
cs


'알고리즘 > BOJ' 카테고리의 다른 글

[백준] 2336 굉장한 학생  (0) 2018.06.17
[백준] 12930 두 가중치  (0) 2018.06.16
[백준] 2099 The game of death  (0) 2018.06.15
[백준] 1165 도로포장  (0) 2018.06.06
[백준] 15806 영우의 기숙사 청소  (2) 2018.06.05
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/12   »
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
글 보관함