회의실 배정문제에서 조건을 간선으로 표현하는 과정에서 질문 드립니다 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는 회의 해야한다. 이렇게 간선을 추가하면 오답이 뜨던데 왜 꼭 위의 형태로 간선을 추가해야하는거죠?? 둘다 똑같이 문제에서 필요로 하는조건(주간 혹은 월말 둘중에 하나는 회의를 해야한다, 겹칠 경우 둘중에 하나만 해야한다) 이지 않나요?? 7년 전
2개의 댓글이 있습니다. keith 문제 이름을 알려주시면 좀더 정확히 알려드릴 수 있을텐데, 일반적인 회의실 배정이라면 Greedy 하게 푸는것을 말씀하시는건가요? (제가 저 책이 없이 풀고 있어서... ㅜㅜ) 만약 Greedy하게 푸는거라면, 단순 정렬 문제일텐데..^^; 7년 전 link tennie 엇 관심가져주셔서 감사합니다 ㅜㅜ 아 그 문제가 아니라 그래프 dfs로 푸는 문제입니다. 알고스팟에서 문제 ID는 MEETINGROOM 이네요!! 7년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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는 회의 해야한다.
이렇게 간선을 추가하면 오답이 뜨던데
왜 꼭 위의 형태로 간선을 추가해야하는거죠??
둘다 똑같이 문제에서 필요로 하는조건(주간 혹은 월말 둘중에
하나는 회의를 해야한다, 겹칠 경우 둘중에 하나만 해야한다)
이지 않나요??
7년 전