[프로그래머스] 방문 길이 - Python

해당 문제는 Summer/Winter Codding(~2018)에 출제된 문제로 Level 2에 해당한다. 11 by 11 Matrix로 구성된 좌표 평면에서 캐릭터가 이동하고, 캐릭터가 지나간 길 중 처음 걸어본 길의 길이를 구하는 문제다.

 

 

입력이 'ULURRDLLU'로 주어졌다면, 아래와 같이 그려볼 수 있고, 8과 9에 해당하는 이동은 처음 걸어본 길이 아니기 때문에 빼고 값은 7이 된다. 

 

두 번째 예시의 경우, 벽에 붙은 경우에는 이를 무시한다.

 

 

해당 문제는 좌표 평면 + 집합으로 계산하면 쉽게 해결이 가능하다. 집합을 통해 시작 지점과 끝 지점을 양방향 그래프, 무향 그래프로 표현하고 전체 길이에서 2를 나누게 되면 처음 방문한 거리가 나온다. 만약에 문제에서 방향 까지 고려한다고 했으면, 코드를 조금 수정하면 쉽게 풀이할 수 있다. 

 

def solution(dirs):
    loc = {'U':(0, 1), 'D':(0, -1), 'R':(1, 0), 'L':(-1, 0)}
    answer = set()
    x, y = 0, 0
    for d in dirs:
        dx, dy = loc[d]
        nx, ny = x + dx, y + dy
        
        if abs(nx) <= 5 and abs(ny) <= 5:
            answer.add((x, y, nx, ny))
            answer.add((nx, ny, x, y))
            x = nx 
            y = ny
            
    return len(answer) // 2