회의실 배정문제에서 조건을 간선으로 표현하는 과정에서 질문 드립니다

  • tennie
    tennie

    알고리즘 문제 해결 전략 책에 있는 풀이 코드를 보면서 이해하고 있는데 궁금한 점이 있어서 질문드립니다.
    그래프를 만들때보면 조건식에 의해
    (j=i+1)
    adj[i * 2 + 1].push_back(j * 2);
    //주간이 회의 안하면 월간은 해야한다.

    adj[j * 2 + 1].push_back(i * 2);
    //월간이 회의 안하면 주간은 해야한다.

    겹칠경우
    adj[i * 2].push_back(j * 2 + 1);

    //i가 회의 하면 j는 회의 하면 안된다.

    adj[j * 2].push_back(i * 2 + 1);

    //j가 회의 하면 i는 회의 하면 안된다.

    와 같이 간선을 표현하는데 이걸 그냥 반대로해서

    adj[i * 2].push_back(j * 2+1);
    //주간이 회의 하면 월간은 안해야한다.

    adj[j * 2].push_back(i * 2+1);
    //월간이 회의 하면 주간은 안해야한다.

    겹칠경우
    adj[i * 2+1].push_back(j * 2);

    //i가 회의 안하면 j는 회의 해야한다.

    adj[j * 2+1].push_back(i * 2);

    //j가 회의 안하면 i는 회의 해야한다.

    이렇게 간선을 추가하면 오답이 뜨던데
    왜 꼭 위의 형태로 간선을 추가해야하는거죠??
    둘다 똑같이 문제에서 필요로 하는조건(주간 혹은 월말 둘중에
    하나는 회의를 해야한다, 겹칠 경우 둘중에 하나만 해야한다)
    이지 않나요??


    1주 전
2개의 댓글이 있습니다.
  • keith
    keith

    문제 이름을 알려주시면 좀더 정확히 알려드릴 수 있을텐데,
    일반적인 회의실 배정이라면 Greedy 하게 푸는것을 말씀하시는건가요?
    (제가 저 책이 없이 풀고 있어서... ㅜㅜ)
    만약 Greedy하게 푸는거라면, 단순 정렬 문제일텐데..^^;


    1주 전 link
  • tennie
    tennie

    엇 관심가져주셔서 감사합니다 ㅜㅜ 아 그 문제가 아니라 그래프 dfs로 푸는 문제입니다. 알고스팟에서 문제 ID는 MEETINGROOM 이네요!!


    1주 전 link
  • 댓글을 남기시려면 로그인하세요.