Lv5. 방의 개수

# 문제 설명

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

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

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

# 제한 사항

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

# 입출력 예

입출력 예 설명

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

문제 해결 시 고려사항

• 지나갔던 경로에 대한 처리(방향 정보 저장)

본 문제는 원점으로 시작하여 주어지는 방향 정보에 따른 이동으로 발생하는 선분들로 인해 생기는 공간의 개수를 카운트하는 문제이다. 단순히 생각하면 선분 간의 교차점을 통해 공간 생성 유무를 판단할 수 있지만, 지났던 방향을 다시 지나게 된다면 그 또한 교차로 판단되어 카운트 될 것이다.

따라서, 본 문제는 이동 간의 이동 방향에 대한 정보를 계속해서 저장하며 탐색해야 하는 문제인 것이다. 문제의 풀이 과정은 아래와 같다.

1. arrows 방향에 대해 방향정보,방문여부를 딕셔너리 및 큐에 저장

    chck, direc, q = {}, {}, deque()
    chck[(0, 0)] = 0
    q.append([0, 0])
    x, y, ans = 0, 0, 0
    # arrows 방향에 대해 방향정보,방문여부를 딕셔너리 및 큐에 저장
    for i in arrows:
      for j in range(2):
        currx = x + dx[i]
        curry = y + dy[i]
        chck[(currx, curry)] = 0
        direc[(x, y, currx, curry)] = 0
        direc[(currx, curry, x, y)] = 0
        q.append([currx, curry])
        x, y = currx, curry
        x, y = q.popleft()
        chck[(x, y)] = 1
   

2. 현재 위치와 다음 위치에 대한 검사 실시

    while q:
      # 현재 위치와 다음 위치에 대한 검사 실시
      nx, ny = q.popleft()
      # 이동할 위치가 방문한 적이 있고
      if chck[(nx, ny)] == 1:
        # 전에 이동을 했던 방향이 아니라면
        if direc[(x, y, nx, ny)] == 0:
          # 답 증가, 해당 구간 이동여부 변경
          ans += 1
          direc[(x, y, nx, ny)] = 1
          direc[(nx, ny, x, y)] = 1
          # 이동할 위치에 방문한적이 없다면
          else:
            # 해당 위치 방문 여부 변경 및 해당 구간 이동여부 변경
            chck[(nx, ny)] = 1
            direc[(x, y, nx, ny)] = 1
            direc[(nx, ny, x, y)] = 1
            # 현재 위치를 이동할 위치였던 좌표로 변경
            x, y = nx, ny
   

3. 위의 반복을 통해 카운트 한 정답 반환

    return ans
   

   
   

전체 코드

from collections import deque
# 방향 정보 리스트
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
def solution(arrows):
    chck, direc, q = {}, {}, deque()
    chck[(0, 0)] = 0
    q.append([0, 0])
    x, y, ans = 0, 0, 0
    # arrows 방향에 대해 방향정보,방문여부를 딕셔너리 및 큐에 저장
    for i in arrows:
        for j in range(2):
            currx = x + dx[i]
            curry = y + dy[i]
            chck[(currx, curry)] = 0
            direc[(x, y, currx, curry)] = 0
            direc[(currx, curry, x, y)] = 0
            q.append([currx, curry])
            x, y = currx, curry
    x, y = q.popleft()
    chck[(x, y)] = 1
    while q:
        # 현재 위치와 다음 위치에 대한 검사 실시
        nx, ny = q.popleft()
        # 이동할 위치가 방문한 적이 있고
        if chck[(nx, ny)] == 1:
            # 전에 이동을 했던 방향이 아니라면
            if direc[(x, y, nx, ny)] == 0:
                # 답 증가, 해당 구간 이동여부 변경
                ans += 1
                direc[(x, y, nx, ny)] = 1
                direc[(nx, ny, x, y)] = 1
        # 이동할 위치에 방문한적이 없다면
        else:
            # 해당 위치 방문 여부 변경 및 해당 구간 이동여부 변경
            chck[(nx, ny)] = 1
            direc[(x, y, nx, ny)] = 1
            direc[(nx, ny, x, y)] = 1
        # 현재 위치를 이동할 위치였던 좌표로 변경
        x, y = nx, ny
    return ans