[문제리뷰] 방문 길이-python ; (programmers/Lv2)

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

프로그래머스

 

방문 길이 - 중복 없이 지나온 경로의 개수

[문제 분석]
(주어진 값) "UDRL"이 중복되어 적힌 문자열 dirs, 좌표값의 범위 x,y는 [-5,5] 안에 있다. 
(U: 위쪽으로 한 칸 가기 / D: 아래쪽으로 한 칸 가기 / R: 오른쪽으로 한 칸 가기 / L: 왼쪽으로 한 칸 가기)

(목표) (0,0)에서 주어진 값에 따라 좌표 이동했을 때, 좌표평면 내 범위 안의 값 중 중복되지 않는 경로의 개수 세기

(전략) 이동한 좌표의 시작점과 끝점을 중복 없이 리스트에 기록하여 그 개수를 세기
1. 초기 x,y 좌표를 설정한다. 그리고 이동경로를 담을 빈 리스트를 생성한다.   : (0,0), result = []
2. dirs의 문자에 따른 이동 방향을 디렉토리로 설정한다. : {"문자" : (x축 이동, y축 이동)} 
3. 2번에 의해 이동된 새로운 좌표를 nx,ny로 설정한다. 
4. 새로운 좌표가 범위(-5 <= x,y <=5)에 들어오는 지 조건을 확인한다.
5. 해당 이동 경로가 이전에 지나간 적이 없는 지 조건을 확인한다. 
6. 이전에 지나간 적이 없으면(5번 조건) *양뱡향*의 좌표 이동 정보를 저장한다. 
7. 범위안에 들어오면(4번 조건) 현재의 좌표값 x,y 값을 새로운 좌표 nx,ny로 갱신한다. 
(주의: 이전에 지나간 경로일 지라도 범위에 들어온다면 좌표값이 갱신되어야 한다.)
8. 이동경로를 담은 리스트의 길이를 **2로 나눈 값**을 리턴한다. 
*양방향인 이유는 지나갔던 경로이기에 방향에 상관없기 때문이다. 
**양방향의 좌표 이동값을 리스트에 담았기 때문에 최종 결과물에서는 중복된 경로를 2로 나눔으로써 제거한다. 

dirs = 'ULURRDLLU'

from pprint import pprint
def solution(dirs):
    x,y = 0,0 
    result = []
    dir = {'U':(0,1),"D":(0,-1),"R":(1,0),"L":(-1,0)}
    for d in dirs:
        nx = x+dir[d][0]
        ny = y+dir[d][1]
        if (-5<=nx<=5 and -5<=ny<=5):
            if ([(x,y),(nx,ny)] not in result):
                result.append([(x,y),(nx,ny)])
                result.append([(nx,ny),(x,y)])
            x,y = nx, ny
    
    pprint(result)
    return len(result)//2

dirs = 'ULURRDLLU'
# dirs = "LULLLLLLU"
solution(dirs) # 7

 

(저장된 좌표 경로를 출력한 결과물)

[[(0, 0), (0, 1)],
[(0, 1), (0, 0)],
[(0, 1), (-1, 1)],
[(-1, 1), (0, 1)],
[(-1, 1), (-1, 2)],
[(-1, 2), (-1, 1)],
[(-1, 2), (0, 2)],
[(0, 2), (-1, 2)],
[(0, 2), (1, 2)],
[(1, 2), (0, 2)],
[(1, 2), (1, 1)],
[(1, 1), (1, 2)],
[(1, 1), (0, 1)],
[(0, 1), (1, 1)]]