프로그래머스 - 방문 길이 (핵심 : line 체크)

💡문제 분석 요약

• 위 아래 왼쪽 오른쪽 명령어가 들어오면 해당 좌표로 이동한다.
• 이동하지 못하는 위치라면, 즉 벗어났다면 해당 명령은 무시한다.
• 이때 새로운 길에 대해서 체크한다. 갔던 길을 다시 가는 것은 count하지 않는다.

💡알고리즘 설계

• 처음엔 전형적인 DFS인줄 알았으나, 이미 주어진 명령어와 범위가 있어서 DFS까지는 안써도 되는 거로 인식했다.
• 다만 왔던 길인지 알아야하므로 visited같은 역할을 하는 자료구조가 필요했고, 이는 set()을 사용했다.

💡코드

def operation(x, y, op):
    if op == "U":
        y += 1
    elif op == "D":
        y -= 1
    elif op == "R":
        x += 1
    elif op == "L":
        x -= 1
    return x, y

def isValid(x, y):
    if x < 0 or x > 10 or y < 0 or y > 10: # 벗어난다면
        print("벗어났습니다.")
        return False
    return True

def solution(str):
    ans = 0
    x, y = 5, 5
    road = set() # 방문처리


    for direction in str:
        nx, ny = operation(x, y, direction) # 해당 방향으로 이동할 수 있느냐, 없느냐를 따져야하므로 nx ny를 먼저 구해야함

        if isValid(nx, ny) == False: # 새로운 좌표가 벗어났으면 무시함. (현재 좌표를 넣고 비교하는 건 의미 없음. 현재는 valid해서 이미 도달한 거니까)
            continue
        if (x, y, nx, ny) not in road and (nx, ny, x, y) not in road:
            road.add((x, y, nx, ny))
            road.add((nx, ny, x, y))
            ans += 1 # 새로운 길이니까 추가
        x, y = nx, ny # 새로운 좌표값으로 업데이트

    return ans


print(solution("ULURRDLLU")) # 7
print(solution("LULLLLLLU")) # 7

💡시간복잡도

• dirs 길이만큼 수행되므로 일단 O(N)인데, 그 안에서 수행되는 것들이 다 if라서 O(1)이라 전체 시간복잡도는 O(N)이 된다.

💡 틀린 이유, 수정

• DFS로 풀려고 했다가 실패
• 처음엔 하나하나의 좌표로 생각했음. 그렇게 하니까 A->B하고 처음 가는 길인 C ->B가 있어도 이미 B가 체크된 상태라 C->B를 새로운 길이라고 인식하지 않는 문제가 있었음.
• 좌표가 아니라 길로써 인식하여 visited를 A->B, B->A 이렇게 서로의 길에 대해 체크해줬음.

💡 느낀점 or 기억할정보

• set에 ( ) 형태로 통째로 넣는 것 알고가기