[프로그래머스] 방의 개수
문제
이해
입력
- 이동할 방향을 담은 배열
- 배열 크기:
[1, 10만] - 원소 범위:
[0, 7]에 속하는 자연수 - 원소의 의미: 12시를
0으로 하여, 시계방향으로 $45^\circ$씩 돌아갈 때마다 +1을 한 값
- 배열 크기:
출력
- 방의 개수
규칙
- 원점(0,0)에서 시작해서 숫자가 적힌 방향으로 선을 긋는다.
- 사방이 막히면 방 하나로 샌다.
예시
입력: [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]
출력: 3
접근
brute-force
만약 사람처럼 시각적으로 방을 판단하고자 한다면 비어있는 공간 내부에 대하여 DFS 또는 BFS를 해보는 아이디어가 있을 수 있다. 그런데 입력으로 주어지는 원소의 개수가 최대 10만개나 된다. 제곱하면 100억이므로 O(n^2) 알고리즘조차 거부하겠다는 말이다. 문제의 경우 직선 상의 정점 뿐만이 아니라, 그 내부의 비어있는 정점까지 살펴봐야 한다. DFS나 BFS를 통하여 위와 같은 상태공간을 탐색하는 것은 O(n^2)의 시간복잡도에 해당한다. 따라서 이런 방식으로 해결할 수 없다.
그런데 문제에서 주어진 예시를 살펴보면 자신이 지나온 점을 다시 방문할 때 새로운 폐곡선이 하나씩 생긴다는 것을 알 수 있다. 또한 한 번 지나간 직선은 다시 지나가도 새롭게 그려지는 것이 없기 때문에 제외해야 한다는 사실도 알 수 있다. 이런 사항을 구현하면 다음과 같다.
def solution(arrows):
dirs = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
cache, arrow_cache = set([(0, 0)]), set()
answer, y, x = 0, 0, 0
for arrow in arrows:
ny, nx = y + dirs[arrow][0], x + dirs[arrow][1]
# print(f'{(y, x)}->{(ny, nx)}')
if not (ny, nx) in cache:
# print('처음 방문하는 노드')
cache.add((ny, nx))
arrow_cache.add((y, x, arrow))
arrow_cache.add((ny, nx, (arrow + 4) % 8))
elif not (y, x, arrow) in arrow_cache:
# print('방문한 적은 있는데 이 방향으로 방문한 적은 없음')
answer += 1
arrow_cache.add((y, x, arrow))
arrow_cache.add((ny, nx, (arrow + 4) % 8))
y, x = ny, nx
return answer
그런데 통과가 안 된다.
테스트케이스를 여러가지 넣어보고 제출했다고 생각했는데 빠트린 것이 있었다.
문제의 조건을 다시 읽어보니 [7, 4, 1]과 같은 입력도 충분히 가능했다. 예시 그림을 본 후로 무의식적으로 두 직선이 반드시 정점 위에서만 교차한다고 생각하고 있었던 것이다.
결론적으로, 대각선으로 직선을 그릴 때 이 직선과 수직한 직선을 기록해 두고, 기록해둔 직선을 다시 그리는 경우에 추가로 answer += 1을 해주는 방식으로 문제를 해결할 수 있었다.
그런데 이보다 훨씬 우아한 풀이법도 있다!
기하학
문제를 해결하고 다른 사람의 풀이를 보았는데 이게 뭐지? 싶은 풀이가 있었다. 단순하게 점과 선의 수를 셀 뿐인 코드였는데, return 값이 점과 선의 수를 통해 계산되어지는 것이었다. 이 풀이를 보고 문득 오일러의 다면체 정리가 생각났다.
오일러의 다면체 정리는 임의의 다면체에 대하여 꼭짓점 개수(v) - 모서리 개수(e) + 면의 개수(f) = 2가 성립한다는 정리이다. 물론 우리가 문제에서 다루는 그래프는 다면체는 아니지만, 이런 접근 방법이 존재할 수 있겠다는 영감을 얻었다.
문제에서 하나의 직선을 그을 때 1개의 선과 1개의 점을 방문하게 된다. 이를 일반화하기 위해 가장 간단한 경우를 생각해보자. 한 쪽 방향으로만 쭉 긋게 되면 v - e = 1이 된다. 처음 시작 정점인 (0, 0)도 세기 때문이다. 그런데 직선을 긋다가 기존에 방문한 적이 있는 점에 닿게 되는 경우에는 성립하지 않는다. 선이 추가되는 것은 같지만, 점 대신 방이 추가 되기 때문이다. 따라서 기존 공식에 방의 개수 r을 추가하면 된다! v - e + r = 1이 성립하므로 답은 1 - v + e가 된다.
구현
brute-force
def solution(arrows):
dirs = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
cache, arrow_cache, cross_cache = set([(0, 0)]), set(), set()
answer, y, x = 0, 0, 0
def cross(y, x, arrow):
y1, x1, y2, x2 = 0, 0, 0, 0
arrow1, arrow2 = (arrow + 2) % 8, (arrow + 6) % 8
if arrow == 1:
y1, x1 = y - 1, x
y2, x2 = y, x + 1
elif arrow == 3:
y1, x1 = y, x + 1
y2, x2 = y + 1, x
elif arrow == 5:
y1, x1 = y + 1, x
y2, x2 = y, x - 1
elif arrow == 7:
y1, x1 = y, x - 1
y2, x2 = y - 1, x
else:
return
if not (y1, x1, arrow1) in arrow_cache:
cross_cache.add((y1, x1, arrow1))
if not (y2, x2, arrow2) in arrow_cache:
cross_cache.add((y2, x2, arrow2))
for arrow in arrows:
ny, nx = y + dirs[arrow][0], x + dirs[arrow][1]
# print(f'{(y, x)}->{(ny, nx)}')
if (y, x, arrow) in cross_cache:
# print(f'교차하면서 방 생기는 경우: {(y, x, arrow)}')
answer += 1
cross_cache.remove((y, x, arrow))
cross_cache.remove((ny, nx, (arrow + 4) % 8))
if not (ny, nx) in cache:
# print('처음 방문하는 노드')
cache.add((ny, nx))
arrow_cache.add((y, x, arrow))
arrow_cache.add((ny, nx, (arrow + 4) % 8))
cross(y, x, arrow)
elif not (y, x, arrow) in arrow_cache:
# print('방문한 적은 있는데 이 방향으로 방문한 적은 없음')
answer += 1
arrow_cache.add((y, x, arrow))
arrow_cache.add((ny, nx, (arrow + 4) % 8))
cross(y, x, arrow)
y, x = ny, nx
return answer
기하학
def solution(arrows):
dirs = [(-2, 0), (-2, 2), (0, 2), (2, 2), (2, 0), (2, -2), (0, -2), (-2, -2)]
v, e = set([(0, 0)]), set()
y, x = 0, 0
for arrow in arrows:
ny, nx = y + dirs[arrow][0], x + dirs[arrow][1]
my, mx = (ny + y) // 2, (nx + x) // 2
v.update([(my, mx), (ny, nx)])
e.update([tuple(sorted(li)) for li in [[(y, x), (my, mx)], [(my, mx), (ny, nx)]]])
y, x = ny, nx
return len(e) - len(v) + 1
갑자기 코드가 많이 바뀌어서 구현 디테일에 대한 주석이 필요할 것 같다. 먼저 위에서 언급한 정점이 아닌 곳에서 교차하는 경우를 체크하기 위해 grid를 2배로 늘렸다. 이렇게 하면 기존에 한 번에 그릴 직선을 두 번에 나눠 그리는 것이 된다. 또한 edge를 기록할 때, 가능한 두 방향을 모두 등록하는 대신, 방향이 없는 선분을 등록하기 위하여 좌표를 정렬하여 넣었다.
댓글남기기