[Python] programmers 방문 길이- 좌표 이동 구현

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

코딩테스트 연습 - 방문 길이

 

 

 

 

def solution(dirs):

    x, y = 0, 0    # 시작점
    ways = ['00']    # 들린 위치의 좌표

    # L, R, U, D에 따른 이동 방향
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    move_types = ['D', 'U', 'L', 'R']  # 각 방향의 index D:0, U:1, L:2, R:3 

    # 이동 계획을 하나씩 확인
    for dir in dirs:

        # 이동 후 좌표 구하기
        for i in range(len(move_types)):

            if dir == move_types[i]:   # 해당되는 무브타입에서
                x += dx[i]          # 그에 맞게 방향 갱신
                y += dy[i]

            # 공간을 벗어나는 경우 무시
            if dir == move_types[i] and ((abs(x) > 5) or (abs(y) > 5)):
                x -= dx[i]          
                y -= dy[i]   
                continue

        ways.append(str(x)+str(y))	 - ⓐ

    answer = 0
    visited = []

    for i in range(len(ways) - 1):

        a = (ways[i], ways[i+1])
        b = (ways[i+1], ways[i])	- ⓑ

        if a not in visited and b not in visited and a != b: - ⓒ

            visited.append(a)
            visited.append(b)

            answer += 1
    
    return answer

 

 코딩 교재의 좌표 이동 시뮬레이션을 한 코드를 참고해서 직접 짜본 코드이다. (비록 코드가 길고 비효율적이라고 생각이 들지만 구현 파트에 대해 조금이나마 익숙해질 수 있었다.)

 

ⓐ - ways에 append된 좌표점들은 이동 계획인 dirs에 따라 잘 적용되었다

 

하지만 본 문제는 한번 지난 길을 겹치지 않게 세는 문제(이동 방향과 무관하게)였고 이 부분을 해결하기가  특히 어려웠다.

 

ⓑ - 먼저 ways에 입력되 좌표들을 현재위치와 나중위치를 튜플로 만들어 변수 a에, 시점을 바꿔서 튜플로 변수 b에 할당했다. (이동 방향과 무관하게 길을 지났는지 여부를 세기위해)

 

ⓒ - a나 b가 visited에 포함되지 않는 경우와 a와 b가 다른 경우(a와 b가 같은 경우는 범위 밖을 벗어난 경우이다)에 방문하지 않은 길이므로 해당 길의 데이터를 visited에 append하고 answer에 1을 더해준다.

 

 

 

 

다음은 다른 분이 작성한 정답 코드이다.

x, y = [0, 0, -1, 1 ], [1, -1, 0, 0]
d = {"U":0, "D":1, "L":2, "R":3}

def solution(dirs):

    answer = 0
    visited = []
    position = (0,0)
    
    for command in dirs:
        i = d[command]
        new = (position[0]+x[i],position[1]+y[i])
        
        if (abs(new[0]) > 5) or (abs(new[1])) > 5: 
        	continue
        if (position,new) not in visited: 
            visited.append((position,new))
            visited.append((new,position))
            answer += 1
            
        position = new
        
    return answer

 

좌표 위를 이동하는 것을 시뮬레이션하기 위한 코드로 딕셔너리를 활용했고 이 경우 코드가 더 간결해짐을 알 수있었다.

 

방문한 길을 판단하는 부분은 이 코드의 아이디어를 참고했다.