[자료구조] 방문 길이 파이썬 (hash)

def solution(dirs):
    
    
    x,y = 5,5 # start point
    mapping = {"U":(0,1), "D":(0,-1), "R":(1,0), "L":(-1,0)}
    
    

    visited = [[0 for _ in range(11)] for _ in range(11)]

    
    
    for i,d in enumerate(dirs):
        
        
        if 0 <= x+mapping[d][0] <= 10 and 0 <= y+mapping[d][1] <= 10:
            x,y = x+mapping[d][0],y+mapping[d][1]
            
            if not visited[x][y]:
                visited[x][y] = i

            
    ans = 0
    for i in visited:
        ans += sum(1 for x in i if x > 0)

    return ans+1

이런식으로 풀었는데 절반만 맞고 틀리다고 나온다.

 

---

정답이 이런식으로 푼다고 나오는데 일단 이 방법을 기억해두고 다른 풀이도 찾아보자.

def solution(dirs):
    x, y = 0, 0 # 시작 좌표를 0, 0으로 지정
    map = dict() # 좌표를 키로 사용하는 해시 생성
    for command in dirs: # O(dirs)
        if command == 'U' and y < 5: # 위로
            map[(x, y, x, y+1)] = True # 현재 좌표, 이동할 좌표
            # x, y 좌표 작은게 왼쪽으로~
            y += 1
        elif command == 'D' and y > -5: # 아래로
            map[(x, y-1, x, y)] = True # 이동할 좌표, 현재 좌표
            y -= 1
        elif command == 'R' and x < 5: # 오른쪽으로
            map[(x, y, x+1, y)] = True # 현재 좌표, 이동할 좌표
            x += 1
        elif command == 'L' and x > -5: # 왼쪽으로
            map[(x-1, y, x, y)] = True # 이동할 좌표, 현재 좌표.
            x -= 1

    return len(map) # 추가된 값들이 곧 방문 길이

dict으로 이렇게 만들면 결국 중복되는 key의 value가 계속 True로 주면 된다는 점이다.

---