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

문제 요약

캐릭터는 (0, 0)에서 시작해 U, D, R, L 명령에 따라 이동한다.

• 이동 가능한 좌표 범위는 -5 <= x, y <= 5이다.
• 범위를 벗어나는 이동 명령은 무시한다.
• 이미 지나간 길을 다시 지나가더라도 한 번만 센다.
• 같은 길을 반대 방향으로 지나간 경우도 이미 방문한 길이다.

처음 방문한 길의 개수를 반환하면 된다.

핵심 아이디어

이 문제에서 중복 여부는 좌표가 아니라 두 좌표를 잇는 길을 기준으로 판단해야 한다.

예를 들어 (0, 0) -> (0, 1)을 지나간 뒤 (0, 1) -> (0, 0)으로 돌아오면, 두 이동은 방향만 다를 뿐 같은 길이다.

따라서 한 번의 이동을 아래처럼 저장한다.

((현재 x, 현재 y), (다음 x, 다음 y))

그리고 반대 방향도 함께 집합에 넣는다.

paths.add(((x, y), (nx, ny)))
paths.add(((nx, ny), (x, y)))

이렇게 저장하면 같은 길을 어느 방향으로 다시 지나가도 집합에서는 중복으로 처리된다. 실제 경로 하나를 양방향으로 두 번 저장하므로, 최종 집합 크기를 2로 나눈 값이 답이다.

풀이 과정

1. 현재 좌표를 (0, 0)으로 초기화한다.
2. 명령어에 따라 다음 좌표를 계산한다.
3. 다음 좌표가 경계를 벗어나면 해당 명령을 무시한다.
4. 범위 안이라면 현재 좌표와 다음 좌표를 연결한 경로를 집합에 양방향으로 저장한다.
5. 현재 좌표를 다음 좌표로 이동한다.
6. 집합 크기를 2로 나누어 반환한다.

Python 코드

def solution(dirs):
    # 명령어별 좌표 변화량
    move = {
        "U": (0, 1),
        "D": (0, -1),
        "R": (1, 0),
        "L": (-1, 0),
    }

    x, y = 0, 0
    paths = set()

    for command in dirs:
        dx, dy = move[command]
        nx = x + dx
        ny = y + dy

        # 경계 밖으로 나가는 이동은 무시한다.
        if nx < -5 or nx > 5 or ny < -5 or ny > 5:
            continue

        # 같은 길을 반대 방향으로 이동해도 중복으로 처리하기 위해
        # 양방향 경로를 모두 저장한다.
        paths.add(((x, y), (nx, ny)))
        paths.add(((nx, ny), (x, y)))

        x, y = nx, ny

    return len(paths) // 2

예시

dirs = "ULURRDLLU"인 경우를 살펴보자.

• 2번, 3번 이동으로 (0, 1) <-> (1, 1) 경로를 지난다.
• 8번, 9번 이동은 이미 지나간 경로를 반대 방향으로 다시 이동한다.

집합에는 같은 경로가 추가되지 않으므로 처음 방문한 길의 수는 7이다.

시간 복잡도

N을 명령어 문자열의 길이라고 하자.

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

각 명령어를 한 번씩 확인하고, 집합의 삽입과 조회는 평균적으로 O(1)이다.

정리

방문한 지점을 세는 문제가 아니라 방문한 길을 세는 문제다. 경로를 양방향으로 저장하면, 방향이 다른 동일한 길을 간단하게 하나로 처리할 수 있다.