[알고리즘][3] 방의 개수

문제 설명
원점(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

나의 풀이

- 방이 만들어지는 조건을 잘 구현하는 것이 중요한 문제

- set을 활용해 중복 제거

from collections import defaultdict

def solution(arrows):
    # 그래프 구현 문제
    # 그려나가면서 만약에 방이 생기면 하나로 센다
    # 방인 줄 아는 알고리즘이 필요하다
    # 이런 문제에서는 크기를 두 배로 넓히는 것이 좋다
    # (x, y)를 하나의 노드로 보고 이를 키값으로 했을 때 value는 이와 직접 연결되는 노드를 가리킨다
    
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    dy = [-1, -1, 0, 1, 1, 1, 0, -1]
    graph = defaultdict(set)
    visited = set()
    
    x, y = 0, 0
    visited.add((x, y))
    answer = 0
    for arrow in arrows:
        for i in range(2):
            nx = x + dx[arrow]
            ny = y + dy[arrow]
            if (nx, ny) in visited and (nx, ny) not in graph[(x, y)]:
                answer += 1
            else:
                
                visited.add((nx, ny))
            
            graph[(x, y)].add((nx, ny))
            graph[(nx, ny)].add((x, y))
            
            x = nx
            y = ny
    
    return answer

- 과거의 풀이를 참조해보니 굳이 visited라는 것을 따로 만들 필요 없이 key값을 이용해주면 된다. 이를 고려해 리팩토링하면 다음과 같다.

- key 값을 활용할 수도 있다!

from collections import defaultdict

def solution(arrows):
    # 그래프 구현 문제
    # 그려나가면서 만약에 방이 생기면 하나로 센다
    # 방인 줄 아는 알고리즘이 필요하다
    # 이런 문제에서는 크기를 두 배로 넓히는 것이 좋다
    # (x, y)를 하나의 노드로 보고 이를 키값으로 했을 때 value는 이와 직접 연결되는 노드를 가리킨다
    
    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 arrow in arrows:
        for i in range(2):
            nx = x + dx[arrow]
            ny = y + dy[arrow]
            if (nx, ny) in graph and (nx, ny) not in graph[(x, y)]:
                answer += 1
            
            graph[(x, y)].add((nx, ny))
            graph[(nx, ny)].add((x, y))
            
            x = nx
            y = ny
    
    return answer

Reference

---

https://ggjggj.tistory.com/187

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