====== 방의 개수 ======

===== 풀이 =====
  * 더 간단한 풀이를 알게 되어서 업데이트.
  * 기존의 풀이는 화살표 방향으로 이동하다가 이전에 지나간 점 위를 다시 지나간 횟수를 방의 개수로 계산하는 방식이었다. 여태가지 이동한 직선의 목록 L과 점의 목록 P를 유지하면서, 새로 이동한 경로(도착점이 p고 직선이 l인)가 l∉L 이고 p∈P 이면 방의 갯수를 하나 증가시키는 식으로 구현했었다.
  * 그런데 이것을 더 단순히 하면 그냥 마지막까지 이동을 해보면서, 경로안의 모든 직선의 집합 L과 모든 점의 집합 P의 최종값을 계산해 놓고, 그 P와 L의 크기만 이용해서 답을 바로 구할수 있다. 이동한 경로가 l∈L, p∈P 이거나 l∉L, p∉P 일때는 |L|-|P|가 변하지 않고, l∉L,p∈P 이어서 방의 갯수를 증가시켜야 할때에만 |L|-|P|도 1만큼 증가한다. 따라서 처음의 |L|-|P| 와 마지막의 |L|-|P|값의 차이가 방의 갯수가 되는 것.
  * 사실 이것은 이렇게 번거롭게 증명하지 않아도 V-E+F=2 라는 오일러 공식에 대입하면 바로 나온다. 공간의 갯수 F = E-V+2 = |L|-|P|+2 이고, 문제에서의 방은 폐공간만 세어야 하니 저기에서 1을 빼야 한다. 즉 답은 |L|-|P|+1.

++++ 기존에 적었던 풀이 |
  * 로직은 간단하다. 화살표 방향으로 이동하다가 이전에 지나간 점 위를 다시 지나간 횟수가 방의 개수이다.
    * 지나갔던 선 위를 그대로 지나가는 경우는 제외.
  * 구현도 간단하다. 이전에 지나갔던 점을 모두 저장해서 유지하면서, 새로 이동할 때마다 지금 이동하는 직선 위에 있는 점들이 이전에 지나간 적이 있는 점인지만 확인하면 된다.
  * 조금 신경써야 할 부분은 대각선으로 겹치는 경우의 처리와 지금 이동한 직선이 이전에 이동했던 직선인지의 체크.
  * 대각선이 없으면, 한번 이동할 때마다 끝점이 이전에 이동한 적 있는 점인지만 체크하면 되지만, 대각선으로 이동할 때에는 x자 형태로 격자의 중간점이 겹칠 수도 있어서 끝점만 확인해서는 안된다. (x,y) -> (x+1,y+1)로 이동하는 경우에는 이전에 (x,y+1)->(x+1,y)로 이동한적이 있는지를 체크하는 식으로 처리할 수도 있지만, 코드가 지저분해진다. 중점에서도 겹치고 끝점에서도 겹치는 경우도 또 고려해야 한다. 좀더 깔끔하게 하려면, 대각선 이동의 경우 (x,y) -> (x+0.5,y+0.5) -> (x+1,y+1)로 두번 이동하는 것으로 생각해서 처리하는 방법이 있다. 그러면 (x+0.5,y+0.5)와 (x+1,y+1)이 둘 다 이전에 지나간 적이 없는지를 체크하고, 이동한 점 목록에도 두 점을 모두 추가하는 식이다. 물론 격자의 한칸을 2라고 생각해서 중점도 정수 좌표가 되게 저장하는게 깔끔하다.
  * 지금 이동한 직선이 이전에 이동했던 직선인지를 체크하려면, 이동했던 직선들도 따로 저장해서 갖고 있어야 한다. 그리고 (x0,y0) -> (x1,y1)로 이동할때, (x0,y0)->(x1,y1)과 (x1,y1)->(x0,y0) 이 모두 이동한 적이 없는 직선임을 체크해야 한다. 직선을 저장하는 set과 점을 저장하는 set를 따로 갖고 있도록 구현할수도 있지만, 여기에서는 dict[(int,int), set[(int,int)]] 형태의 dict하나를 이용해서, 각 점과 그 점과 연결된 직선들의 목록을 저장하도록 구현했다.
  * 한칸 이동할때마다, 지금 이동하는 점과 직선이 방문한 적 있는지만 O(1)에 체크하면 되니까, 전체 시간 복잡도는 O(이동횟수)이다.
++++


===== 코드 =====
==== 코드 1 - 최신 방식 (이동을 모두 마치고 방의 갯수를 계산) ====
<dkpr py>
"""Solution code for "Programmers 49190. 방의 개수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/49190
- Solution link: http://www.teferi.net/ps/problems/programmers/49190
"""

MOVES_BY_ARROW = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0),
                  (-1, -1)]


def solution(arrows):
    cur_point = (0, 0)
    edges = set()
    points = set([cur_point])
    for arrow in arrows:
        dx, dy = MOVES_BY_ARROW[arrow]
        for _ in range(2):
            next_point = (cur_point[0] + dx, cur_point[1] + dy)
            points.add(next_point)
            edges.add((min(cur_point, next_point), max(cur_point, next_point)))
            cur_point = next_point
    # from Euler's formula, V-E+F=2
    return len(edges) - len(points) + 1
</dkpr>

==== 코드 2 - 예전 방식 (이동할 때마다 체크해서 방의 갯수를 갱신) ====
<dkpr py>
"""Solution code for "Programmers 49190. 방의 개수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/49190
- Solution link: http://www.teferi.net/ps/problems/programmers/49190
"""

import collections

MOVES_BY_ARROW = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0),
                  (-1, -1)]


def solution(arrows):
    neighbors_by_point = collections.defaultdict(set)
    room_count = 0
    point = (0, 0)
    neighbors_by_point[point] = set()
    for arrow in arrows:
        for _ in range(2):
            new_point = (point[0] + MOVES_BY_ARROW[arrow][0],
                         point[1] + MOVES_BY_ARROW[arrow][1])
            if ((neighbors := neighbors_by_point.get(new_point)) is not None and
                    point not in neighbors):
                room_count += 1
            neighbors_by_point[new_point].add(point)
            neighbors_by_point[point].add(new_point)
            point = new_point
    return room_count
</dkpr>

{{tag>프로그래머스 ps:problems:programmers:Level_5}}