MEETINGROOM 알고책 873페이지 질문점,,

  • cjkis
    cjkis

    https://algospot.com/judge/problem/read/MEETINGROOM

    // 그래프의 인접 리스트 표현
    vector<vector<int> > adj;
    
    // 두 구간 a 와 b 가 서로 겹치지 않는지를 확인한다
    bool disjoint(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second <= b.first || b.second <= a.first;
    }
    
    // meetings[] 가 각 팀이 하고 싶어하는 회의 시간의 목록일 때, 이를 
    // 2-SAT 문제로 변환한 뒤 함축 그래프를 생성한다.
    // i번 팀은 meetings[2*i] 혹은 meetings[2*i+1] 중 하나 시간에 회의실을 써야 한다.
    void makeGraph(const vector<pair<int, int> >& meetings) {
        int vars = meetings.size();
    
        // 그래프는 각 변수마다 두 개의 정점을 갖는다.
        adj.clear(); adj.resize(vars * 2);
    
        for (int i = 0; i < vars; i += 2) {
            // 각 팀은 i번 회의나 j번 회의 둘 중 하나는 해야 한다.
            // (i or j) 절을 추가한다.
            int j = i + 1;
            adj[i * 2 + 1].push_back(j * 2); // ~i=>j
            adj[j * 2 + 1].push_back(i * 2); // ~j=>i
        }
    
        for (int i = 0; i < vars; i++)
        for (int j = 0; j < i; j++) {
            // i번 회의와 j번 회의가 서로 겹칠 경우
            if (!disjoint(meetings[i], meetings[j])) {
                // i번 회의가 열리지 않거나, j번 회의가 열리지 않아야 한다.
                // (~i or ~j) 절을 추가한다.
                //printf("meetings %d and %d overlap\n", i, j);
                adj[i * 2].push_back(j * 2 + 1); 
                adj[j * 2].push_back(i * 2 + 1);
            }
        }
    }
    

    makeGraph() 함수 질문인데여,,

    아래는 문제에 나온 세번째 입력데이터입니다
    3
    2 5 6 9
    1 3 8 10
    4 7 11 12

    이 경우 makeGraph() 함수의 파라미터 meetings의 값은 pair로 아래와 같이 6개가 됩니다
    i meetings[i]
    0 (2, 5)
    1 (6, 9)
    2 (1, 3)
    3 (8, 10)
    4 (4, 7)
    5 (11, 12)

    makeGraph() 함수의 아래 부분이 이해가 잘 안되네용,,

        for (int i = 0; i < vars; i += 2) {
            // 각 팀은 i번 회의나 j번 회의 둘 중 하나는 해야 한다.
            // (i or j) 절을 추가한다.
            int j = i + 1;
            adj[i * 2 + 1].push_back(j * 2); // ~i=>j
            adj[j * 2 + 1].push_back(i * 2); // ~j=>i
        }
    
    1. 주석을 보면 i or j 절을 추가한다고 되어있습니다. 그런데 adj[i], adj[j]에 값을 대입한 것이 아니라 adj[i*2 + 1], adj[j*2 +1]에 값을 대입하네요. 왜 i,j 에 값을 넣지 않고, i*2+1, j*2+1 배열에 값을 넣었는지 궁금합니다.

    2. 그리고 오른쪽 주석을 보면 ~i=>j로 되어있는데요, 그렇다면 i*2+i는 ~i를 나타내고, j*2는 j를 나타내는 건가요?
      그런데 j를 나타내는 거라면 push_back으로 j를 넣어야 하는것 아닌가요? 어째서 j*2를 push_back으로 넣었는지 궁금합니다,,

    3. adj[3].push_back(0) 의 의미는 meetings[3]이 true면 meetings[0]도 true가 된다는 의미가 맞나요?


    9년 전
2개의 댓글이 있습니다.
  • chaos.kite
    chaos.kite
    1. i번회의 j번회의 각각 i,~i j,~j의 두정점으로 표현됩니다 adj.resize(vars*2);도 같은 이유입니다
    2. 1번과 같은 이유
    3. 3 = ~(1번회의), 0 = (0번회의) 즉, 1번회의가 false이면 0번회의는 true이다 입니다 위 code에서 i가 1, j가 0인 경우네요

    9년 전 link
  • cjkis
    cjkis

    감사합니다


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.