방의 개수
Prov
선을 그은 후 폐곡선 갯수 구하기
Solv
- 한 번 방문했던 노드를 다시 방문
선분을 오고 갔는지 구분 불가 - 선분인 경우를 구분하는 방법
선을 그릴 때 양 끝 노드를 key값으로 하는 딕셔너리의 value인 리스트에 추가하고 그 노드의 리스트에 새로운 노드가 있는지 확인 - 대각선 처리
범위를 2배로 해서 대각선의 겹치는 부분이 노드가 되도록 해결
Check
(0,0), (1,0), (0,1)을 지나는 삼각형 경우
(0,1)->(0,0)의 과정에서 (0,0)의 리스트에 (0,1)이 포함되어 있지 않음
따라서 폐곡선이 맞음
| (0,0)->(1,0) | {(0,0) : [(1,0)], (1,0) : [(0,0)]} |
| (1,0)->(0,1) | {(0,0) : [(1,0)] (1,0) : [(0,0),(0,1)], (0,1) : [(1,0)]} |
| (0,1)->(0,0) | {(0,0) : [(1,0),(0,1)] (1,0) : [(0,0),(0,1)], (0,1) : [(1,0),(0,0)]} |
(0,0), (0,1)을 지나는 선분의 경우
(0,1)->(0,0)의 과정에서 (0,0)의 리스트에 (0,1)이 포함되어 있음
따라서 폐곡선이 아님
| (0,0)->(0,1) | {(0,0) : [(0,1)], (0,1) : [(0,0)]} |
| (0,1)->(0,0) | x |
