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

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

프로그래머스

def solution(dirs):
    visited = set()
    direction =  {'U': (1, 0), 'D': (-1, 0), 'R': (0, 1), 'L': (0, -1)}
    y, x = 0, 0

    for d in dirs:
        dy, dx = direction[d]
        ny, nx = y + dy, x + dx
        if -5 <= ny < 6 and -5 <= nx < 6:
            visited.add(((y, x), (ny, nx)))
            visited.add(((ny, nx), (y, x)))
            y, x = ny, nx

    return len(visited) // 2

 

처음엔 딕셔너리에 방향을 저장하고 bfs로 풀었다.
근데 답이 안나와서 방문 지점을 다 그려보니
(0,0) (1,0) (1,-1), (2,-1), (2,0) (2,1) (1,1) (1,0)
이렇게 나오는걸 볼 수 있는데 1,1에서 1,0으로 간 적이 없는데 1,0을 방문했기에 이 루트는 더해지지 않았었다.
결국 답을 찾아보았는데 set을 이용해서 훨씬 더 간편하게 풀 수 있다는 것을 알게되었다.

 

set을 이용해서 방문한 지점을 방문 처리하는게 아니라 방문한 간선을 처리해주었다.
A -> B를 이동한건 B -> A로 이동한것과 같기 때문에 두개 다 set에 넣어주고 실제 방문한 거리는 이를 2로 나누는 것이니 이를 2로 나눠줬댜!

 

 

 

문제 보고 쉽다고 생각했눈데!! 아직 더 알고리즘을 풀어봐야겠댜 ㅠㅠ
얼른 알고리즘 왕마니 풀어서 알고리즘 다 뿌수고 다녀야짐~!