문제 보기 · Level 5 · 고득점 Kit · 그래프 · 정답률 8% · 푼 사람 3,273명 (2026-09-30 기준)1
문제
원점 (0, 0)에서 시작해 arrows에 적힌 방향으로 한 칸씩 움직이며 선을 긋는다. 방향 0은 위, 1은 오른쪽 위이고, 시계 방향으로 돌아 7은 왼쪽 위다. 선으로 사방이 막힌 곳을 방 하나로 센다. 방의 개수를 돌려준다.
- arrows 길이 1 ~ 100,000, 원소 0 ~ 7
- 방 안에 다른 방이 있을 수 있다
풀이
막히면 한 단계씩 펼친다2.
1단계 · 작은 예로 손으로 풀기
- [2, 0, 6, 4]: 오른쪽, 위, 왼쪽, 아래로 정사각형을 한 바퀴 돈다. 방은 1개다. 마지막 선이 이미 지나간 원점에 닿으면서 방이 닫힌다.
- [2, 0, 6, 4, 2, 0]: 같은 선을 다시 그어도 방은 늘지 않는다. 그대로 1개다.
- [1, 4, 7]: 오른쪽 위로 (1, 1), 아래로 (1, 0), 왼쪽 위로 (0, 1)에 간다. 두 대각선이 (0.5, 0.5)에서 엇갈려 작은 삼각형 방이 1개 생긴다. 그런데 지나간 점끼리는 한 번도 다시 만나지 않는다.
방은 “새 선이 이미 있던 점에 닿을 때” 생긴다. 다만 대각선이 엇갈리는 곳처럼 점이 아닌 곳에서 닫히는 방도 있다.
2단계 · 가장 단순한 방법과 그 속도
그림을 모눈에 촘촘히 점으로 찍어 그린다. 선이 아닌 칸을 덩어리로 묶고, 바깥 덩어리 하나를 뺀 수를 센다. 답은 맞지만 화살표 10만 개면 그림이 가로세로 수만 칸까지 커진다. 한 칸을 점 6×6으로 찍으면 점이 수백억 개라 어림없다.
3단계 · 핵심 아이디어
- 오일러 공식: 선이 모두 이어진 그림에서 점 수를 V, 선 수를 E, 바깥까지 넣은 영역 수를 F라 하면 V − E + F = 2다(오일러 공식, Euler’s formula). 방은 바깥을 뺀 F − 1 = E − V + 1개다. 한 붓으로 그린 그림이라 선은 늘 모두 이어져 있다.
- 선을 하나씩 더하며 세기: 새 선이 새 점으로 가면 E와 V가 함께 1 늘어 방 수는 그대로다. 새 선이 이미 있던 점으로 가면 E만 1 늘어 방이 하나 는다. 이미 그은 선을 다시 지나가면 아무것도 바뀌지 않는다.
- 트리와 랭크로 보기: 새 점으로 가는 선만 모으면 모든 점을 잇는 트리(신장 트리)가 된다. 방 수 E − V + 1은 이 트리 밖에 남는 선의 수다. 선마다 두 끝점에 1과 −1을 적은 행을 쌓은 행렬(근접 행렬)로 보면, 트리 선의 행 V − 1개는 서로 독립이다. 나머지 선의 행은 이들을 더하고 빼서 만든다. 그래서 랭크는 V − 1이고, 방 수는 선 수에서 랭크를 뺀 값이다(랭크와 네 부분공간).
- 반 칸으로 나누기: 오일러 공식은 선이 만나는 곳마다 점이 있어야 맞는다. 가로·세로 선은 대각선과 끝점에서만 만난다. 그런데 방향이 다른 두 대각선은 칸 한가운데 (0.5, 0.5) 같은 곳에서 엇갈린다. 한 칸 이동을 반 칸씩 두 번으로 나누면(좌표를 두 배로 보면) 이 엇갈리는 곳도 점이 된다.
- 집합에 기록: 지나간 점과 선을 집합에 넣는다. 선은 방향이 없으니 두 끝점을 작은 것부터 적어, 갔다 오는 선을 같은 선으로 센다.
4단계 · 코드 흐름
- points = {(0, 0)}, edges = 빈 집합, rooms = 0.
- 화살표마다 같은 방향으로 반 칸씩 두 번 간다.
- 한 번 갈 때마다 선 (지금 점, 다음 점)을 작은 점이 앞에 오게 적는다.
- 처음 보는 선이면, 다음 점이 points에 이미 있을 때 rooms를 1 늘린다. 그리고 선과 점을 집합에 넣는다.
- 다 그리면 rooms를 돌려준다.
5단계 · 파이썬 코드
MOVES = ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)) # 0 위, 시계 방향
def solution(arrows):
x, y = 0, 0
points = {(0, 0)}
edges = set()
rooms = 0
for d in arrows:
dx, dy = MOVES[d]
for _ in range(2): # 한 칸을 반 칸씩 두 번 간다
nx, ny = x + dx, y + dy
e = ((x, y), (nx, ny)) if (x, y) < (nx, ny) else ((nx, ny), (x, y))
if e not in edges:
if (nx, ny) in points:
rooms += 1 # 새 선이 이미 있던 점에 닿으면 방이 하나 닫힌다
edges.add(e)
points.add((nx, ny))
x, y = nx, ny
return rooms
for _ in range(2): 한 번에 dx, dy만큼 두 번 움직인다. 좌표 전체를 두 배로 늘린 그림을 그리는 셈이다.(x, y) < (nx, ny): 튜플은 첫 값부터 비교하고, 같으면 다음 값을 비교한다. 작은 점을 앞에 두면 (a, b)와 (b, a)가 같은 선이 된다.- 튜플은 바뀌지 않는 값이라 집합에 넣을 수 있다. 리스트 [x, y]는 넣을 수 없다.
6단계 · 실행 추적
[1, 4, 7]을 두 배 좌표로 그린다.
| 화살표 | 선 | 처음 보는 선? | 다음 점이 이미 있나 | rooms |
|---|---|---|---|---|
| 1 (첫 반 칸) | (0, 0) – (1, 1) | 예 | 아니오 | 0 |
| 1 (둘째 반 칸) | (1, 1) – (2, 2) | 예 | 아니오 | 0 |
| 4 | (2, 2) – (2, 1) | 예 | 아니오 | 0 |
| 4 | (2, 1) – (2, 0) | 예 | 아니오 | 0 |
| 7 | (2, 0) – (1, 1) | 예 | 예 | 1 |
| 7 | (1, 1) – (0, 2) | 예 | 아니오 | 1 |
두 배 좌표의 (1, 1)이 원래 그림의 (0.5, 0.5), 곧 대각선이 엇갈리는 곳이다. 답은 1이다.
7단계 · 복잡도와 흔한 실수
화살표마다 집합 연산 몇 번이라 \(O(n)\)이다. 무작위 화살표 10만 개와, 같은 정사각형을 2만 5천 번 도는 화살표 10만 개를 합쳐 0.1초쯤 걸렸다.
- 반 칸으로 나누지 않는다. [1, 4, 7]에서 0이 나온다.
- 선은 안 보고 “이미 있던 점에 닿았나”만 본다. 같은 선을 다시 지날 때도 방을 센다. [2, 0, 6, 4, 2, 0]에서 1 대신 5가 나온다.
- 선을 방향 있게 적는다. 갔다가 되돌아오는 선을 새 선으로 본다. [2, 6]에서 0 대신 2가 나온다.
검증: 문제의 예시, 1단계의 세 예, 6단계 표, 7단계의 세 가지 실수를 코드로 확인했다. 무작위 화살표 1,500묶음(30개 이하)과 좁은 곳을 맴돌며 선을 겹쳐 그리는 500묶음(40개 이하)에서 “그림을 점으로 찍어 막힌 덩어리를 세는” 풀이와 결과가 같았다. 화살표 10만 개의 시간도 쟀다 — 23_pg49190_p1.py