문제

문제 설명

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

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

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

제한사항

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

풀이 아이디어

1) 선을 긋는 것을 어떻게 표현할까?

- 선을 긋는다고 생각하지 말고 다른 방법을 떠올려보자.

2) 방을 찾으려면 어떤 방법을 써야할까?

- 기존의 점과 만날 때 방이 하나씩 생긴다?

3) 대각선이 교차하는 경우는 어떻게 할까?

- ㅠㅠ... 풀이를 참고했다. (그래도 레벨5 치고는 쉬운 편인 듯 싶다)
- " 이동거리를 2로 하면 중간에 노드 하나가 생기게 된다...! 즉 2)의 아이디어를 이용할 수 있다!

4) 왔다갔다 하는 것도 처리해야한다! (문제 풀다 발견함. 테스트케이스 1개는 심했다!)

코드

from collections import defaultdict
def solution(arrows):
    answer = 0
    visit = defaultdict(list)
    x,y = 0,0
    dx,dy = [0,1,1,1,0,-1,-1,-1],[1,1,0,-1,-1,-1,0,1]

    for arrow in arrows:
        for _ in range(2):              # 대각선 판별을 위해 2씩
            nx = x + dx[arrow]
            ny = y + dy[arrow]  
            if (nx,ny) in visit and (x,y) not in visit[(nx,ny)]:    # 방문했던 점이지만 경로가 겹치지 않는 경우, 방+1
                answer += 1
                visit[(x,y)].append((nx,ny))
                visit[(nx,ny)].append((x,y))
            elif (nx,ny) not in visit:                  # 방문하지 않았던 경우
                visit[(x,y)].append((nx,ny))            # 경로가 겹치는 경우는 따로 해줄 필요 없음
                visit[(nx,ny)].append((x,y))
            x,y = nx, ny        # 이동
    return answer