# 테페리넷

## 테페리넷

### 관리자 전용

ps:problems:programmers:49190

# 방의 개수

ps
링크https://programmers.co.kr/learn/courses/30/lessons/49190
출처프로그래머스
문제 번호49190
문제명방의 개수
레벨Level 5
분류

구현

시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python
해결날짜2021/01/22

## 풀이

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

기존에 적었던 풀이

## 코드

### 코드 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 + dx, cur_point + 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

### 코드 2 - 예전 방식 (이동할 때마다 체크해서 방의 갯수를 갱신)

"""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 + MOVES_BY_ARROW[arrow],
point + MOVES_BY_ARROW[arrow])
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

## 토론

댓글을 입력하세요:
E M W S O

ps/problems/programmers/49190.txt · 마지막으로 수정됨: 2021/03/25 14:25 저자 teferi

### 문서 도구 