BOJ-11975 Build Gates

울타리 선분을 겹치지 않는다는 조건이 있으면

• (세워야 하는 최소 울타리문 개수) = (나뉘어진 영역의 개수) - 1
  • 예를 들면 사각형 모양 울타리 하나만 있으면 바깥 영역, 안쪽 영역으로 2개의 영역이 있고 문은 1개가 필요함
  • 울타리를 만드는 와중에 이미 갔던 곳을 또 간다 == 영역의 개수가 하나 늘어났다
• 중복 방문하는 "점"이 얼마나 있는지만 세면 된다
• 방문한 좌표를 1차원 정수로 인코딩해서 배열에 넣고 정렬하면 쉬움

실제 문제

• 울타리 선분이 겹치는 경우를 생각해야 한다
• "안 겹치는 조건에서의 풀이"를 쓰게 되면 겹치는 울타리 선분이 하나 늘어날 때마다 답보다 1만큼 커짐
• 따라서 중복된 울타리 선분의 개수를 세줘서 빼주면 된다
• 울타리 선분의 종류를 한 좌표당 N->S, W->E이 두 가지 경우로 생각해서 무방향 울타리 선분을 1차원 정수로 인코딩해서 배열에 넣고 정렬