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

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

방의 개수

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

문제 단순화

• arrows 배열이 있다.
• 0~7 까지 시계 방향으로 2차원 좌표를 이동한다.
• arrows 배열의 요소대로 선을 그을 때, 생기는 방의 개수를 리턴한다.

문제풀이

• 좌표가 중복될 때마다 방이 하나씩 생성된다.
• 정사각형을 대각선으로 두 번 자르면, 방이 4개가 생성된다.
• 좌표를 벗어나 겹치는 경우를 포함하기 위해서 좌표사이에 새로운 좌표를 둔다.
• 한 번에 2번씩 이동하여 새로운 좌표를 거쳐서 선이 그어지게 만든다.
• 간선이 중복되는 경우 중복되는 정점이 늘어나지만, 방의 개수를 늘어나지 않는다.
• 중복되는 정점의 수와 중복되는 간선의 수를 구한다.
• 중복되는 정점의수 - 중복되는 간선의 수를 리턴한다.

코드

def solution(arrows):
    answer = 0
    visited = [(0,0)]
    edges = []
    actions = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]

    for arrow in arrows:
        for _ in range(2):
            x,y = visited[-1]
            act_x, act_y = actions[arrow]
            visited.append((x+act_x,y+act_y))
            if visited[-2] < visited[-1]:
                edges.append((visited[-2],visited[-1]))
            else:
                edges.append((visited[-1],visited[-2]))

    overlap_edges = len(edges) - len(set(edges))
    overlap_visited = len(visited) - len(set(visited))

    answer = overlap_visited - overlap_edges

    return answer