[알고리즘][2][X] 방의 개수

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

스크린샷 2018-09-06 오후 4.55.33.png

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
입출력 예 설명
스크린샷 2018-09-06 오후 5.08.09.png

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

 

나의 풀이

- 다시 풀어도 아이디어가 생각이 안났다.

- defaultdict를 이용해서 이미 방문한 건 key로 넣고 그거랑 이어지는 거는 value로 넣으면 연결 관계를 나타낼 수 있다는 것을 배웠다. 특히 closed 도형을 구할 때 유용한 방법이다.

from collections import defaultdict

def solution(arrows):
    # 그래프 문제
    # 탐색도 해야 하는 문제
    # 방의 개수를 세는 탐색 알고리즘을 구상하는게 핵심인 문제
    # 보통 이런 문제는 graph의 크기를 두 배로 해주면 됨
    
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    dy = [-1, -1, 0, 1, 1, 1, 0, -1]
    
    visit = defaultdict(list)
    
    answer = 0
    x, y = 0, 0
    for arrow in arrows:
        for i in range(2):
            nx = x + dx[arrow]
            ny = y + dy[arrow]
            
            if (nx, ny) in visit and (x, y) not in visit[(nx, ny)]:
                answer += 1
            visit[(x, y)].append((nx, ny))
            visit[(nx, ny)].append((x, y))

            
            x = nx
            y = ny
    
    return answer