[프로그래머스/파이썬] 방의 개수

 

 

나의 풀이

from collections import defaultdict

def solution(arrows):
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    dy = [1, 1, 0, -1, -1, -1, 0, 1]
    graph = defaultdict(set)
    x, y = 0, 0
    answer = 0

    for cmd in arrows:
        for _ in range(2):
            X = x + dx[cmd]
            Y = y + dy[cmd]
            if (X, Y) in graph and (x, y) not in graph[(X, Y)]:
                answer += 1
            graph[(x, y)].add((X, Y))
            graph[(X, Y)].add((x, y))
            x, y = X, Y

    return answer

 

 

오일러의 공식을 이용한 풀이 1

def solution(arrows):
    point=set([(0,0)])
    line=set()
    move=[[0,2],[2,2],[2,0],[2,-2],[0,-2],[-2,-2],[-2,0],[-2,2]]
    pre_point=(0,0)
    for A in arrows:
        next_point=(pre_point[0]+move[A][0],  pre_point[1]+move[A][1] )
        mid_point=(pre_point[0]+move[A][0]//2,  pre_point[1]+move[A][1]//2 )
        point.add(next_point)
        point.add(mid_point)
        line.add((pre_point,mid_point))
        line.add((mid_point,pre_point))
        line.add((mid_point,next_point))
        line.add((next_point,mid_point))
        pre_point=next_point
    answer = len(line)//2-len(point)+1
    return answer if answer>=0 else 0

 

 

 

오일러의 공식을 이용한 풀이 2

def get_direction(arrow):
    dirs = [ (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1) ]
    return dirs[arrow]

def get_plane_cnt(V, E):
    return 2 - V + E

def solution(arrows):
    vertex = set()
    edge = set()
    (x, y) = (0, 0)
    vertex.add((x, y))

    for arrow in arrows:
        for i in range(2):
            direction = get_direction(arrow)
            (nx, ny) = ( x + direction[0], y + direction[1] )
            s = (x, y)
            e = (nx, ny)

            if e < s:
                s = (nx, ny)
                e = (x, y)

            vertex.add((nx, ny))
            edge.add((s, e))
            (x, y) = (nx, ny)


    answer = get_plane_cnt(len(vertex), len(edge)) -1
    return answer