글이 깁니다 ㅈㅅ합니다

일단 이 질문의 대상은
1. 종만북 2권 (SCC, 2-SAT) 을 마스터했으며
2. 빡치게 긴글이지만 한번 읽어보고 알린이한테 자비를 베풀 용의가 있는 갓갓님
임을 밝혀둡니다.

글이 길기때문에 음슴체 사용하겠습니다 양해 부탁드립니다
------------------------------------

종만북 MEETINGROOM 문제의 함의그래프(implication graph) 에서 막혔음.

일단 나름대로 코드 흐름을 이해하고 재구현하는데, 그냥 앵무새처럼 따라하긴 싫어서 조금씩 바꿔서 구현 해봤음.

아래 코드는 종만북의 "2-SAT 문제의 함의 그래프 만들기" 코드인데.
주황색 볼드체가 원래 종만북 코드고 진분홍색이 내가 바꾼 코드임

*클릭하면 크게보여유




i 와 -i 는 그 부서의 오전시간 회의를 열수있느냐(i) 없느냐(-i)를 나타내는 변수고 j 와 -j는 오후회의를 열수 있느냐 없느냐를 나타내는데.

종만북에서는 -i -> j 라고, 즉 오전 회의가 안 열리면(-i) 오후 회의는 열린다(j) 라고 한것이고
나는 i -> -j 라고, 즉 오전이 열리면 오후는 안열린다고 했음.

내가 이해한게 맞다면 저렇게 바꿔도 별 탈이 없어야 하거든. 별탈이 없어야 하는데...

저렇게 바꾼 코드로 그래프를 만들면 이렇게 됨





왼쪽이 종만북코드로 만든 그래프고 오른쪽이 내꺼 그래프. 빨간색이 워래 종만북에서 바뀐 간선임

내꺼는 보다시피 사이클이 하나도 없음. 타잔 알고리즘 돌려보면 SCC id가 12종류가 됨. 즉 scc가 사실상 없음. 모든 Vertex 가 다 따로놈.

함의그래프의 i * 2 이 파트 너무빡세서 계속 반복해서 보는중인데 저 부분을 주의해야한다는 내용은 안보이거든.

그리고 내가 이해 하기로도 문제가 없어야 하는데;; 사실 그렇잖아?
오전이 안열린다 -> 오후가 열린다 (종만북)
오전이 열린다 -> 오후가 안열린다 (내코드)
같은뜻 아님? 근데 결과물은 이상하게 나오네

그나마 이와 관련된 내용이 있는 내용은 873p에 나오는데

이런 "P이면 Q이다" 형태의 관계를 고등학교 수학의 논리학 과정에서 필요조건과 충분조건이라고 불렸던 것을 기억하실겁니다. 다음과같이 쓰곤 했지요

0번 회의가 개최되지 않는다(!A0) => 1번회의가 개최된다(A1)
1번 회의가 개최되지 않는다(!A1) => 0번회의가 개최된다(A0)

오, 화살표로군요! 화살표를 보면 이들을 그래프로 표현하고 싶지 않으세요?


보다시피 개최되지않는다 => 개최된다 순서로 implicate 하고있음. 저거 말곤 딱히 힌트나 주의사항같은것도 없는데... 도와줘요 갓갓님들


아래는 푸념글::
지금 2sat 파트에 몇일이나 발목잡혀있는지 모르겠음;; 너무빡침. 그나마 내가 짤막하게나마 이산수학 에 살짝 발이라도 담궈봤기에 이 파트에서 말하는 함의(implicate) 라는게 조건명제(함축명제) 를 말하는거구나 하고 예전에 배운책 뒤져도보고 나무위키도 보고 해서 겨우 이해하는거지 너무 암시적으로 깔려있는 베이스가 너무많음;; 그래프 파트가 특히 더 그런듯.