[구현 알고리즘] 상하좌우 문제

구현

머리속에 있는 알고리즘을 소스코드로 바꾸는 과정
사실 모든 알고리즘 문제가 구현이 필요하다.

알고리즘 문제에서 구현 유형이란?

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

ex. 알고리즘은 간단한데 코드가 길어지는 문제
실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
적절한 라이브러리를 찾아서 사용해야 하는 문제

많은 연습이 필요한 부분임!!!
많은 코드를 작성하고 많은 라이브러리들이 존재하는 것을 미리 공부해 놓아야함!!

일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용된다.
시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

상하좌우 문제

문제 설명

여행가 A는 NxN 크기의 정사각형 공간에 서 있고, 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다.
가장 왼쪽 위 좌표는 (1, 1)이고 가장 오른쪽 아래 좌표는 (N, N)이다.
상하좌우로 이동할 수 있으며, 시작 좌표는 (1,1)이다.

계획서대로 이동하면 되는데
L, R, U, D는 각각 왼쪽, 오른쪽, 위, 아래로 한칸씩 이동하라는 뜻이다.

만약 공간을 벗어나는 움직임이 있다면 그 움직임은 무시하고 다음으로 넘어간다.

내 문제 풀이

계획표를 하나씩 for 문 돌면서 지시사항대로 이동하고
만약 공간의 범위를 넘어간다면 다시 돌아오는 식으로 코드를 짰다.
좀 지저분하게 짜여진 코드 같긴하지만..
결과는 나왔다.

내 코드

n = int(input("공간의 크기 n 입력 (n x n): "))
plan = list(map(str, input().split()))
pos_col = 1;
pos_row = 1;

for i in plan:
  if i =="R":
    pos_row += 1
    if pos_row > n:
      pos_row -=1
  elif  i =="L":
    pos_row -= 1
    if pos_row < 1:
      pos_row +=1
  elif  i =="U":
    pos_col -= 1
    if pos_col < 1:
      pos_col += 1
  elif  i =="D":
    pos_col += 1
    if pos_col > n:
      pos_col -= 1

print(pos_col, ",", pos_row);

정답 코드

# N 입력 받기
n = int(input())
x, y = 1, 1
plans = input(),split()

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)):
    nx = x + dx[i]
    ny = y + dy[i]
  
  # 공간을 벗어나는 경우 무시
  if nx < 1 or ny < 1 or nx > n or ny > n:
    continue
  x, y = nx, ny

print(x, y)

배울점

시뮬레이션 유형으로도 분류 될 수 있는 문제이다.
시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 유사점이 많다.

움직임의 종류를 미리 리스트에 담아두고 방향벡터를 이용하여,
계획서와 움직임의 종류를 비교하여 해당되는 방향벡터만큼 원래의 위치에서 더해서 이동하는 방식

공간을 벗어나는 경우 continue로 빠져나가 넘어가기
공간을 벗어나지 않는 경우라면 현재위치를 업데이트해주기

내 코드로도 결과가 제대로 나왔지만 뭔가 깔끔하지 않다. 깔끔한 방식의 코드를 많이 보고 배우자!!!

Reference

(이코테 2021 강의 몰아보기)2. 그리디 & 구현