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

https://programmers.co.kr/learn/courses/30/lessons/49190

코딩테스트 연습 - 방의 개수

 

오일러 공식이 생각나서 활용하니 맞았다.

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

 

문제로 주어진 조건으로 봤을 때, 대각선으로 변이 교차하는 경우 오일러 공식의 전제 조건인 평면 그래프가 아닐 수 있으므로 1칸이 아니라 2칸으로 그래프를 늘려 1칸마다 꼭짓점으로 생각한다. set 을 이용하여 중복된 꼭짓점 또는 변을 무시하여 정확한 개수를 구한다. 변은 점과 점이 이어진 선으로 중복을 막기 위해서 값을 (x[0] + y[0], x[1] + y[1]) 로 한다. 

 

문제에서 사방이 막혀야 방으로 인정하므로 f = e - v + 2 에서 바깥 평면은 무시되므로 1을 빼준다. 

 

def solution(arrows):
    answer = 0
    d = {0 : (-1, 0), 1 : (-1, 1), 2 : (0, 1), 3 : (1, 1), 4 : (1, 0), 5 : (1, -1), 6 : (0, -1), 7 : (-1, -1)}
    x = (0, 0)
    v = set({x})
    e = set()

    for arrow in arrows:
        for i in range(2):
            y = (x[0] + d[arrow][0], x[1] + d[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

print(solution([6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0])) # 3