목록2-sat (1)
N coding
3654_L퍼즐
타워 디펜스를 풀고나서 이 문제를 풀면 비슷하게 보인다. black인 노드를 기준으로 세로방향(위 t, 아래 f) 가로방향 (왼 t, 아래 f)의 두가지 상태를 가진다. black인 노드의 사방을 보면서 만약 위나 아래중에 하나만 존재한다면 얘는 반드시 그 하나랑 연결되야 하므로 논리식을 세워준다. (black i의 위 or black i의 위) 역시 가로방향도 마찬가지로 해준다. 만약 black i가 위에 잇는 w랑 연결이 된다면 그 w랑 연결될 수 잇는 가능성이 있는 다른 아이들은 다 연결불가이다. 그런 의미에서 w를 타고 들어가서 (black i의 아래 or black j의 ~방향)의 논리식을 세워줬다. 12345678910111213141516171819202122232425262728293031..
PS
2018. 8. 29. 15:55