[Python] 구현 및 시뮬레이션 알고리즘을 파헤쳐 보자! (상하좌우)

문제

• 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다.
• 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있습니다. 각 문자의 의미는 다음과 같습니다.
  
  • L : 왼쪽으로 한 칸 이동
  • R : 오른쪽으로 한 칸 이동
  • U : 위쪽으로 한 칸 이동
  • D : 아래쪽으로 한 칸 이동
• 최종적으로 도착할 좌표(X, Y)를 공백 기준으로 출력합니다.

5 x 5에서 R R R U D D라고 입력학 되면 이러한 순서로 넘어가야 한다.

최종적으로는 3, 4가 출력이 되어야 한다.

입력

5
R R R U D D

출력

3, 4

정답

import sys

n = int(sys.stdin.readline().strip())
move_list = list(sys.stdin.readline().strip().upper().split())

# 이동 타입
move_types = ["L", "R", "U", "D"]

#방향 벡터
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

x, y = 1, 1

for move in move_list:
    for i in range(len(move_types)):
    	# 내가 입력한 이동경로(move_list[n])과 move_types[n]이 같다면
        if move == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]

    # 좌표를 넘어갈 시 넘기기
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue

    x = nx
    y = ny

print(x, y)

Tip

방향벡터

방향벡터는 구현 및 완전 탐색 등에서 많이 쓰이기 때문에 알고 있으면 좋은 개념이다.

2차원 배열과 현재 위치, 이동 방법을 알려준 상태이면 다음과 같이 사용하여 이동할 수 있다.

#방향 벡터
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
x, y = 1, 1

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

 

Reference

본 그리디 알고리즘 문제 예제 및 개념은 나동빈 (이코테 2021 강의 몰아보기)  2. 그리디 & 구현을 참고합니다.