[Problem Solving] 상하좌우

구현

 이번에는 구현에 대한 알고리즘을 공부하였다. 구현 알고리즘 "상하좌우"에 들어가기에 앞서 간단한 사방 탐색으로 시작해볼까 한다. 아래의 코드는 순서대로 우, 상, 좌, 하 순서대로 1, 2, 3, 4를 차례대로 채우는 예제이다. 특히 2차원 배열을 초기화할 때는 반드시 리스트 컴프리 헨션을 이용해 주어야 한다. 그렇지 않으면 데이터를 넣거나 하는 등의 과정에서 문제가 생길 수 있다.

n = 3
m = 3
array = [[0] * m for _ in range(n)]  # 리스트 컴프리 헨션을 이용한 2차원 배열 초기화

# 방향 벡터 이용
dx = [0, -1, 0, 1]  # 행, row
dy = [1, 0, -1, 0]  # 열, column

x, y = 1, 1  # 3 X 3 크기의 2차원 배열에서 1, 1을 기준으로 우, 상, 좌, 하에 순서대로 값을 넣습니다.

cnt = 1  # 들어갈 값

for i in range(4):
    array[x + dx[i]][y + dy[i]] = cnt
    print(f"{cnt} 넣을 위치는 {x + dx[i] + 1}행 {y + dy[i] + 1}열 입니다.")

    cnt += 1

for i in array:
    for j in i:
        print(j, end=' ')  
    print()
    

'''
출력 
0 2 0 
3 0 1 
0 4 0 
'''

 

print에서 end는 이번에 처음으로 알게 되었는데 문장을 출력하고 마지막에 무엇을 쓰고 끝낼지 정할 수 있습니다. 출력 결과는 위와 같이 우, 상, 좌, 하에 순서대로 1, 2, 3, 4가 들어가는 것을 볼 수 있습니다. 그렇다면 오늘 공부했던 알고리즘은 상하좌우 문제입니다.

 

문제 : 상하좌우

 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N). 여행가  A는 상, 하, 좌, 우 방향으로 이동 가능하고, 시작 좌표는 항상 (1, 1)이다. 여행가 A가 이동할 계획이 적힌 계획서에는 다음과 같이 적혀 있다.

L	왼쪽으로 한 칸 이동
R	오른쪽으로 한 칸 이동
U	위로 한 칸 이동
D	아래로 한 칸 이동

 

단, 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 <= 이동 횟수 <= 100)

입력 예시	출력 예시
5 R R R U D D	3 4

 

n = int(input())  # 정사각형 공간을 입력받는다.
x, y = 1, 1  # 시작 좌표는 항상 (1, 1)이므로 1, 1로 x, y 초기화
plans = input().split() # 이동 계획을 입력받는다.

# 상하좌우(L, R, U, D)에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

move_types = ['L', 'R', 'U', 'D']

# 입력받은 이동 계획을 하나씩 조회
for plan in plans:
    for i in range(len(move_types)): 
    	# move_types와 일치하는 plan이 있다면
        if plan == move_types[i]:
        # 이동한 A의 좌표 nx, ny
            nx = x + dx[i]
            ny = y + dy[i]

    # N x N 크기의 정사각형을 벗어나면 움직임은 무시되므로
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue

    #  공간안에 있다면 A의 좌표 이동
    x, y = nx, ny

print(x, y)

'''
입력
5
R R R U D D

출력
3 4
'''

 

위의 내용 중에서 제일 중요한 것은 방향 벡터를 활용 하는게 가장 중요하지 않을까 싶다. 방향 벡터를 통해 조건에 따른 위치를 이동하고 출력해 주면 되는 문제였는데 처음에는 익숙하지 않아서 시간이 조금 걸렸지만 이해를 하고 나니 보다 쉽게 느껴졌 던 것 같다.