Skip to content

Latest commit

 

History

History
107 lines (77 loc) · 3.82 KB

방의_개수.md

File metadata and controls

107 lines (77 loc) · 3.82 KB
Raw

방의 개수

링크


Description

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

방향

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

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

제한사항

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

입출력 예

arrows return
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3

예1

  • (0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 arrows 를 따라 그립니다.
  • 삼각형 (1), 큰 사각형(1), 평행사변형(1) = 3



Solution

DFS를 이용하면 그래프에서 edge들이 다각형을 이뤄 circle을 이루고 있는지 확인할 수 있다. 시작 node부터 DFS를 통해 연결된 node들을 탐색하여 다음 node가 이전에 거쳐온 node라면 circle을 이루는 것으로 볼 수 있다.

다만, 해당 문제에서는 몇 가지를 고려해야 한다.

  1. 다음 node가 이전에 방문했던 node였으나, 직선을 이루고 있는 경우
  2. 각 node의 상하수평 거리를 1이라고 했을 때 중간에서 만나는 경우

2.의 경우 예를 들어 주어진 그래프가 (0, 0), (1, 0), (1, 1), (0, 1), (1, 0), (0, 0), (1, 1)을 차례로 방문한다고 가정해보자. 이 때 방은 (1, 0), (1, 1), (0, 1)로 이루어진 방과 (0, 0), (1, 0), (1, 1)로 이루어진 방, 그리고 (0, 0), (1, 0), (0.5, 0.5)로 이루어진 방과 (0, 1), (1, 1), (0.5, 0.5)로 이루어진 방까지 총 4개의 방으로 구성되게 된다. 이 때 (0.5, 0.5)을 처리해줘야 하는 문제가 있다.

1, 2의 문제를 해결하기 위해 다음과 같은 방법으로 접근한다.

  1. edge들의 set을 정의하여, 해당 edge가 이전에 방문했던 edge인지 확인.
  2. arrows가 주어질 때 node의 좌표를 1단위가 아닌 2단위로 정의하며, 방문했던 node와 edge를 각각 2개, 4개씩 추가.
from collections import deque


def solution(arrows):
    arrows = deque(arrows)
    x, y, answer = 0, 0, 0
    arrowDict = {
        0: (0, 2),
        1: (2, 2),
        2: (2, 0),
        3: (2, -2),
        4: (0, -2),
        5: (-2, -2),
        6: (-2, 0),
        7: (-2, 2)}
    visited_node = set([(x, y)])
    visited_edge = set([])
    num = arrows.popleft()
    stack = [arrowDict[num]]
    
    def check(x, y, h, v):
        nonlocal visited_node, answer
        if ((x, y), (x+h//2, y+v//2)) not in visited_edge:
            answer = answer+1 if (x+h, y+v) in visited_node else answer
            answer = answer+1 if (x+h//2, y+v//2) in visited_node else answer

    def add_node(x, y, h, v):
        nonlocal visited_node
        visited_node.add((x+h, y+v))
        visited_node.add((x+h//2, y+v//2))
        visited_edge.add(((x, y), (x+h//2, y+v//2)))
        visited_edge.add(((x+h//2, y+v//2), (x, y)))
        visited_edge.add(((x+h//2, y+v//2), (x+h, y+v)))
        visited_edge.add(((x+h, y+v), (x+h//2, y+v//2)))

    while stack:
        (h, v) = stack.pop()
        check(x, y, h, v)
        add_node(x, y, h, v)
        x += h
        y += v
        if arrows:
            num = arrows.popleft()
            stack.append(arrowDict[num])
    return answer

제출