방의 개수

• 더 간단한 풀이를 알게 되어서 업데이트.
• 기존의 풀이는 화살표 방향으로 이동하다가 이전에 지나간 점 위를 다시 지나간 횟수를 방의 개수로 계산하는 방식이었다. 여태가지 이동한 직선의 목록 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.

기존에 적었던 풀이

"""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

"""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