[프로그래머스] 방의 개수 - python

방의 개수

문제 설명

원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.

ex) 1일때는 오른쪽 위로 이동

그림을 그릴 때, 사방이 막히면 방하나로 샙니다. 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요.

제한사항

• 배열 arrows의 크기는 1 이상 100,000 이하 입니다.
• arrows의 원소는 0 이상 7 이하 입니다.
• 방은 다른 방으로 둘러 싸여질 수 있습니다.

풀이

처음에는 단순히 방문한 노드를 다시 방문했을 때 방이 만들어지지 않을까 했다. 근데 똑같은 경로를 왕복으로 움직였을 경우엔 방이 만들어지지 않으므로 테스트케이스에서 다 틀렸다.

그리고 빠르게 다른 사람풀이를 봤다 ㅎㅎㅋㅋ

오일러 공식이라는 것을 사용하면 쉽게 풀 수 있다.

v(꼭지점의 개수) - e(변의 개수) + f(면의) 개수 = 2

대각선이 교차하는 경우를 대비해 1칸이 아니라 두 칸씩 늘린다.

바깥 평면은 무시되므로 1을 빼준다.

def solution(arrows):
    answer = 0
    directions = {
        1: (-1, 1), 0: (-1, 0), 7: (-1, -1),
        2: (0, 1), 6: (0, -1),
        5: (1, -1), 4: (1, 0), 3: (1, 1)
    }
    x = (0, 0)
    v = set({x})
    e = set()
    
    for arrow in arrows:
        for i in range(2):
            y = (x[0] + directions[arrow][0], x[1] + directions[arrow][1])
            v.add(y)
            e.add((x[0] + y[0], x[1] + y[1]))
            x  = y
            
    answer = len(e) - len(v) + 1
    return answer

https://sangsangss.tistory.com/186