[Level 2] 방문 길이

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

코딩테스트 연습 - 방문 길이

---

접근

첫 번째로 풀었을 때는 처음 방문한 점이 몇 개인지 출력하는 줄 알았다. (문제를 꼼꼼하게)

그래서 2차원 그래프를 그려 입력되는 명령대로 움직이며 처음 방문한 점을 카운트하였지만 역시 실패했다.

 

계속 실패하여 다른 사람들의 풀이를 참고하였고 그제서야 처음 방문한 길을 카운트하는 것을 알았다.

해당 길을 방문했는지 표시하기 위해 (y, x)에서 (ny, nx)를 지나갔다는 의미로 네 개의 좌표를 튜플 형태로 visited에 담는다. 이때 양방향으로 표시하기 위해 (ny, nx)에서 (y, x)로 갔다는 의미의 좌표도 visited에 담는다.

 

구현

먼저 명령대로 이동할 수 있도록 딕셔너리 형태로 방향을 지정하였다.

이후 명령대로 이동했을 때 범위 안에 있을 때 visited안에 현재 좌표에서 다음 좌표의 길이 처음인지 검사한다.

만약 처음일 때는 양방향으로 visited에 추가하고 answer을 추가한다.

def solution(commands):
    answer = 0
    dy = [-1, 1, 0, 0]
    dx = [0, 0, 1, -1]
    d = {'U':0, 'D':1, 'R':2, 'L':3}
    visited = set()
    cx, cy = 0, 0
    for cmd in commands:
        ny = cy + dy[d[cmd]]
        nx = cx + dx[d[cmd]]
        if ny < -5 or nx < -5 or ny > 5 or nx > 5:
            continue
        if (cy, cx, ny, nx) not in visited:
            visited.add((cy, cx, ny, nx))
            visited.add((ny, nx, cy, cx))
            answer += 1
        cy, cx = ny, nx
    return answer