학습컨텐츠/알고리즘/데이터구조 썸네일형 리스트형 Manhattan (2SAT) Manhattan 당신에게 임무가 주어졌다. 도시의 도로를 디자인 하는 것이다. 당신의 도시에는 수평으로 나있는 도로가 있고 수직으로 나있는 도로가 있어 격자를 이루고 있다. 디자인 한다는 것은 각각의 수평, 수직도로의 방향을 결정하는 것이다. 각 도로는 결정된 단 하나의 방향으로만 이동해야 한다. 또한 시민들은 당신에게 자신들의 요구사항을 말해줄 것이다. '요구'는 자신이 원하는 시작 위치에서 끝 위치까지 단순한 경로가 하나 이상 존재해야 한다는 것이다. 아래의 그림을 보도록 하자. 시민 한사람의 요구사항이 그림과 같을 때 a)는 불가능한 경로이다. 왜냐하면 도로의 방향대로 움직이지 않았기 때문이다. b)는 가능한 경로이긴 하지만 단순한 경로가 아니다. 단순한 경로는 정확히 한 번 굴절된 경로를 말한다.. 더보기 이전 1 다음
