프로그래머스 5레벨 - 방의 개수 <그래프>

페어프로그래밍에서 내가 드라이버를 맡고 수학신 jmpop님이 네비게이터를 하셨다.

https://school.programmers.co.kr/learn/courses/30/lessons/49190#

프로그래머스

문제 설명

원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.
ex) 1일때는 오른쪽 위로 이동

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

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

입출력 예
arrows [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 
return  3 

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

 

---

원점에서 시작, 주어진 배열 방향으로 이동하면서 만나는 점들을 선으로 연결한 후, 방의 개수를 찾아야한다.

< 방으로 count하는 조건 > 

1. 한 번 지나온 점으로 다시 연결될 때

2. 대각선끼리 교차할 때

.
.
.
처음 풀이는 다음과 같다.

def solution(arrows):
  result = 0 # 방의 개수
  now = [0,0] # 현재좌표
  path = [[0,0]] #지나온 경로

  dic_arrows = {  # arrows방향 
    0 : [0,1],
    1 : [1,1],
    2 : [1,0],
    3 : [1,-1],
    4 : [0,-1],
    5 : [-1,-1],
    6 : [-1,0],
    7 : [-1,1]
  }
  for arrow in arrows:  # 배열 순회
    now[0] += dic_arrows[arrow][0]  
    now[1] += dic_arrows[arrow][1]  
    if now in path:  
      result += 1 
    else:
      path.append(now[:]) 
  return result

리스트를 하나씩 탐색하면서 현재좌표 변수에 해당 방향으로 이동한 위치들을 더해주었다. 이동한 위치가 이미 path리스트에 있다면 방 개수 1 증가, 없다면 path리스트에 현재좌표를 추가
(now[:]는 now리스트의 모든 요소를 슬라이싱하여 새로운 리스트를 만들어 반환한다. 이로 인해 path리스트와 now리스트는 서로 영향을 주지 않는다.) 

입출력 예시를 토대로 작성한 코드였는데 입출력 예시만 정상값이 반환되고 실제 실행에서는 실패했다.
알고보니 예외가 조금 더 있었다. 

테스트 케이스

3가지의 테스트 케이스를 준비해서 비교해보았다.

위의 코드로 테스트케이스를 실행했을 때는 
1번 기댓값 : 3 / 결괏값 : 3 => o
2번 기댓값 : 3 / 결괏값 : 1 => x
3번 기댓값 : 3 / 결괏값 : 8 => x 

1번은 입출력 예시코드. 단순히 지나온 점을 만날 때 방 개수를 1씩 추가해주었기에 예외의 경우를 생각해보았다.

추가로 예외처리가 필요한 조건은

(1) 기존의 점을 지나지는 않지만 대각선끼리 교차하여 도형이 생기는 경우
(2) 중복된 경로를 계속해서 지나는 경우  

두 가지의 예외를 생각해서 작성한 코드

def solution(arrows):
  result = 0
  now = [0,0] #현재좌표
  path = [[0,0]]
  

  dic_arrows = {
    0 : [0,1],
    1 : [1,1],
    2 : [1,0],
    3 : [1,-1],
    4 : [0,-1],
    5 : [-1,-1],
    6 : [-1,0],
    7 : [-1,1]
  }
  for arrow in arrows:
    for i in range(4):
      now[0] += (dic_arrows[arrow][0])/4
      now[1] += (dic_arrows[arrow][1])/4
      if now in path:
        if not check:
          result += 1 
        check = True
      else:
        path.append(now[:])
        check = False
  return result

전체적인 부분은 이전 코드와 동일하지만 각 이동 방향별로 4번씩 이동하여 거리를 1로 나누어서 이동시켰다.
방향이 바뀌기 전 이동한 위치가 이미 path리스트에 있으면 check변수를 사용해서 이미 체크한 경로인지 확인해서 중복 경로를 세지 않도록 작성했다.

결과 => 테스트 케이스 3가지 모두 충족했으나 시간복잡도에서 Fail .. 시간복잡도가 0(4n).. ! 




아래는 최종 코드입니다! 

# arrows = [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]  # 3
# arrows = [5, 2, 7, 1, 6, 3]  # 3
# arrows = [6, 0, 3, 0, 5, 2, 6, 0, 3, 0, 5]  # 3

now = [0, 0]    # 현재좌표
dic_arrows = {  # 위치 변경할 때 사용되는 딕셔너리
    0: [0, 1],
    1: [1, 1],
    2: [1, 0],
    3: [1, -1],
    4: [0, -1],
    5: [-1, -1],
    6: [-1, 0],
    7: [-1, 1]
}
path = {}  # 지나온 경로와 해당 경로에 대한 방향을 저장하는 빈 딕셔너리 선언

def check_dia(path, now, arrow):  # 대각선 방향 교차 확인 함수
    c_now = now[:]
    c_arrow = arrow
    if c_arrow > 6:
        c_arrow -= 7
    else:
        c_arrow += 1
    c_now[0] += dic_arrows[c_arrow][0]
    c_now[1] += dic_arrows[c_arrow][1]

    if c_arrow > 2:
        c_arrow -= 3
    else:
        c_arrow += 5

    try:

        c_check_list = path[str(c_now)]
        if c_arrow in c_check_list:
            return True
    except:
        pass
    return False


def solution(arrows):   # 방 개수 구하는 함수
    result = 0
    for arrow in arrows:
        # 이동전
        inline = True
        dic_p = str(now)
        try:
            if arrow not in path[dic_p]:
                path[dic_p] = path[dic_p]+[arrow]
        except:
            path[dic_p] = [arrow]
        # 이동후
        now[0] += dic_arrows[arrow][0]
        now[1] += dic_arrows[arrow][1]
        if arrow > 3:
            arrow = arrow-4
        else:
            arrow = arrow+4
        dic_p = str(now)
        try:
            if arrow not in path[dic_p]:
                path[dic_p] = path[dic_p]+[arrow]
                result += 1
                inline = False
            else:
                inline = True
        except:
            path[dic_p] = [arrow]
            inline = False
        if (arrow % 2 == 1) and (not inline):
            result += check_dia(path, now, arrow)
    return result

print(solution(arrows))

 

 

 

https://jmpop.tistory.com/56