파이썬으로 방문한 좌표를 건너뛰며 로봇이 목표 지점에 도달하는지 확인하는 방법

문제 정의

데카르트 좌표평면의 원점 (0, 0)에 로봇이 서 있다고 가정해 봅시다. 로봇에는 N(북), S(남), W(서), E(동)로 이루어진 이동 명령 목록이 주어집니다. 여기에 독특한 규칙이 하나 있습니다. 로봇이 이미 방문했던 지점에 도달하면, 새로운 미방문 지점에 도달할 때까지 같은 방향으로 계속 직진합니다. 모든 이동을 마친 뒤 로봇이 최종적으로 목표 좌표 (x, y)에 도착하는지 판별하는 것이 이번 문제의 목표입니다.

예시로 이해하기

입력이 다음과 같다고 가정해 보겠습니다.

moves = ['N', 'N', 'E', 'N', 'W', 'S'], coord = [0, -1]

이때 출력은 True입니다. 로봇은 두 칸 북쪽으로, 한 칸 동쪽으로, 다시 한 칸 북쪽으로, 한 칸 서쪽으로, 그리고 한 칸 남쪽으로 이동합니다. 마지막 남쪽 이동 시 바로 아래 좌표는 이미 방문한 곳이므로 로봇은 계속 남쪽으로 전진하고, 그다음 좌표 역시 방문한 곳이라 또 전진하여 결국 (0, -1)에서 멈춥니다.

해결 접근 방식

이 문제의 핵심은 집합(set) 자료구조를 활용해 방문한 좌표를 빠르게 추적하는 것입니다. 집합을 사용하면 특정 좌표의 방문 여부를 평균 O(1) 시간에 확인할 수 있습니다. 알고리즘은 다음과 같이 진행됩니다.

• 현재 위치를 나타내는 nx, ny를 각각 0으로 초기화합니다.
• 방문 좌표를 저장할 집합 l을 생성하고 시작점 (0, 0)을 미리 넣어 둡니다.
• 이동 명령을 하나씩 순회하면서 방향에 맞게 좌표를 갱신합니다. 이때 현재 위치가 이미 집합에 존재하면 같은 방향으로 계속 전진합니다.
• 새로 도달한 좌표를 집합에 추가합니다.
• 모든 이동이 끝나면 최종 좌표 (nx, ny)가 목표 좌표와 일치하는지 비교하여 결과를 반환합니다.

파이썬 구현 코드

class Solution:
    def solve(self, moves, coord):
        ny = nx = 0
        l = {(0, 0)}
        for k in moves:
            if k == "N":
                while (nx, ny) in l:
                    ny += 1
            elif k == "S":
                while (nx, ny) in l:
                    ny -= 1
            elif k == "E":
                while (nx, ny) in l:
                    nx += 1
            else:
                while (nx, ny) in l:
                    nx -= 1
            l.add((nx, ny))
        return coord[0] == nx and coord[1] == ny

ob = Solution()
moves = ['N','N','E','N','W','S']
coord = [0,-1]
print(ob.solve(moves, coord))

실행 결과

True

단계별 동작 추적

예시 입력에 대해 코드가 실제로 어떻게 움직이는지 표로 정리해 보겠습니다.

마지막 S 명령에서 로봇이 지나가는 (0,2), (0,1), (0,0)은 모두 이전에 방문한 좌표이기 때문에 건너뛰고, 처음으로 밟아보는 (0, -1)에서 멈춥니다. 이 값은 목표 좌표 [0, -1]과 정확히 일치하므로 함수는 True를 반환합니다.

복잡도 분석

이동 명령이 n개이고, 한 번의 명령당 최대 건너뛰기 거리를 m이라 할 때 시간 복잡도는 O(n × m)입니다. 공간 복잡도는 방문한 모든 좌표를 집합에 저장해야 하므로 O(n)입니다. 집합 기반 조회 덕분에 각 좌표의 방문 여부 확인이 상수 시간에 처리된다는 점이 이 풀이의 효율성을 좌우합니다.