[알고리즘] 구현(Implementation) / 행렬, 시뮬레이션 문제 접근 방법!

1. 구현(Implementation) 유형의 문제란?

구현 유형의 문제란 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭합니다.

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

 

일반적으로 구현 알고리즘 문제의 2차원 공간은 행렬(Matrix)의 의미로 사용되고 자주 출제됩니다.

행렬이란 2차원 데이터를 일종의 표와 같은 형태로 쉽게 나타내는 수학 개념입니다.
즉, 파이썬에선 2차원 배열을 말합니다.

보통 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향벡터가 자주 활용됩니다.

시뮬레이션 문제같은 경우에는 어떠한 캐릭터나 사물등이 특정 위치에 존재하여 상하좌우로 움직일 수 있다는 문제가 출제하고 방향벡터를 자주 사용합니다. 방향 벡터의 예시를 살펴보겠습니다.

현재 위치 x, y = (2, 2)

     동 북  서 남
dx = [1, 0, -1, 0] # 가로축
dy = [0, -1, 0, 1] # 세로축

동쪽 : 오른쪽 한칸 (2, 2) → (2, 3)
북쪽 : 위쪽 한칸 (2, 2) → (1, 2)
서쪽: 왼쪽 한 칸 (2, 2) → (2, 1)
남쪽: 아래쪽 한큰 (2, 2) → (3, 2)

다음 이동 방향 설정 로직

for i in range(4):
  # 다음 위치
  nx = x + dx[i] # 행 방향
  ny = y + dy[i] # 열 방향
  print(nx, ny)

 

2. <문제> 상하좌우

여행가 A는 N * N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 * 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있습니다. 각 문자의 의미는 다음과 같습니다.

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

이때 여행가 A가 N * N 크기의 정사각형 공간을 벗어나는 움직임은 무시됩니다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시됩니다. 다음은 N = 5인 지도와 계획서입니다.

# 입력
5
R R R U D D

# 출력
3 4

보통 행렬을 사용할 때, (0, 0)부터 사용합니다. 다만, 문제에서 (1, 1)에서 시작한다고 명시한 경우에는 가장 첫 번째 인덱스는 사용하지 않는 방식을 이용하거나, (1, 1)을 소스코드 상에서 (0, 0)으로 처리하여 사용하는 방법도 있습니다.

이 문제는 요구사항대로 충실히 구현하면 되는 문제입니다. 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도 분류되며 구현이 중요한 대표적인 문제 유형입니다. 코테에서는 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많습니다.

# N 입력받기
n = int(input())
x, y = 1, 1 # 현재 위치
plans = input().split() # R R R U D D

# L, R, U, D에 따른 이동 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
move_types = ['L', 'R', 'U', 'D']

# 이동계획 하나씩 확인하기
for i in plans:
    for j in range(len(move_types)):
        if plan == move_types[i]:
            # nx, ny 초기화 불필요
            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)