프로그래머스 - 방문 길이

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

접근

명령 길이가 500개 밖에 되지않고, 각 명령을 실행할 때 갔던 길인지 아닌지만 판단하면 되기 때문에 시뮬레이션으로 했습니다.

중요한건 이미 갔던 길인지 아닌지를 판단하는 과정인데

당연히 지금까지의 루트안에 이 길이 있느냐 를 판단해버리면 시간이 너무 오래걸립니다.

그냥 hash형태로 각 좌표에서 상,하,좌,우를 갔는지 안갔는지만 저장하고

실제로 이동이 가능해서 이동하였을땐 출발지점의 방향과 도착지점의 역방향을 갔다고 판단하면 됩니다.

즉 (0,0)에서 (1,0)으로 갔다면 (0,0)의 U 방향이 1, 그리고 (1,0)의 D방향도 1이 되어야합니다. (방향 상관없이 그 길은 갔다고 판단하기때문)

다음은 코드 전문입니다.

from _collections import defaultdict

def solution(dirs):
    answer = 0
    board = [[0 for _ in range(11)] for _ in range(11)]
    four_ways = [[defaultdict(lambda :0) for _ in range(11)] for _ in range(11)] # U D R L

    dir = dict()
    opposite = dict()

    dir['U'] = [-1,0]
    dir['D'] = [1,0]
    dir['R'] = [0,1]
    dir['L'] = [0,-1]

    opposite['U'] = 'D'
    opposite['D'] = 'U'
    opposite['R'] = 'L'
    opposite['L'] = 'R'
    r = 5
    c = 5
    for i in range(len(dirs)):
        nr = r+dir[dirs[i]][0]
        nc = c+dir[dirs[i]][1]

        if nr < 0 or nr > 10 or nc < 0 or nc > 10:
            continue
        else:
            if four_ways[r][c][dirs[i]] == 0:
                answer += 1
                four_ways[r][c][dirs[i]] = 1
                four_ways[nr][nc][opposite[dirs[i]]] = 1
            r = nr
            c = nc







    return answer