BOJ

BOJ 5214 환승

bsgreentea 2019. 2. 26. 00:04

모든 역 각각의 관계를 그래프로 구성한다면 너무 많은 메모리와 시간이 소모된다.


따라서 각 동일한 튜브에 속했다는 조건을 적절히 사용해주었다.

발코딩이다.


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
// disc[] = 각 역(노드)의 방문 여부
// tube_chk[] = 각 튜브의 방문 여부
int n, k, m, disc[100100], tube_chk[1010];
// tube_list[] = 노드가 속한 하이퍼튜브의 리스트
// tube[] = 각 튜브에 속한 노드(역)의 목록
vector<vector<int>> tube_list, tube;
int main() {
    scanf("%d %d %d", &n, &k, &m);
    tube_list.resize(n + 1);
    tube.resize(m + 1);
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        b = 0;
        for (int j = 0; j < k; j++) {
            scanf("%d", &a);
            tube[i].push_back(a);
            tube_list[a].push_back(i);
        }
    }
    if (n == 1) {
        puts("1"); return 0;
    }
    queue<int> qu;
    qu.push(1);
    disc[1]++;
    int cnt = 1, flag = 0;
    while (!qu.empty()) {
        int qs = qu.size();
        while (qs--) {
            // 현재 위치한 역
            int now = qu.front();
            qu.pop();
            
            // 현재 역이 속한 튜브들을 탐색한다
            for (int now_tube : tube_list[now]) {
                
                // 굳이 해줄 필요는 없을것같다
                if (tube_chk[now_tube]) continue;
                // 현재 역이 속한 튜브가 가진 역들을 탐색한다
                for (int next : tube[now_tube]) {
                    if (disc[next]) continue;
                
                    disc[next] = 1;
                    if (next == n) {
                        flag = 1; break;
                    }
                    if (tube_list[next].size() == 1) continue;
                    qu.push(next);
                }
            }
            if (flag) break;
            // 굳이 해줄 필요는 없을것같다 222
            for (int temp : tube_list[now]) {
                tube_chk[temp] = 1;
            }
        }
        cnt++;
        if (flag) break;
    }
    if (flag)
        printf("%d\n", cnt);
    // 경로가 없다면 -1을 출력
    else
        puts("-1");
}
cs