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

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

프로그래머스

 

무향 그래프, 양방향 그래프라는 점을 고려해서 풀어야 한다. A에서 B로 가는 길과 B에서 A로 가는 길을 동일하게 취급한다.

 

dx, dy 문제와 유사하게 접근하되, 처음 지나간 길의 개수를 알고 싶으므로 집합 자료형을 활용한다.

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

 

정렬을 하는 이유는 1. 방향성 제거 2. 중복 제거다.

1. 방향성 제거

• A → B와 B → A를 동일한 길로 저장하기 위해 정렬을 한다. 방향성이 제거된다.

2. 중복 제거

• 정렬을 통해 항상 같은 순서로 좌표를 저장할 수 있다. 따라서 중복을 한 번 더 제거할 수 있다.