출처: https://youtu.be/puH2p1CQEg4

문제

풀이

이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 예를 들어 이동 횟수가 N번인 경우, 시간 복잡도는 O(N)이다. 따라서 이 문제의 시간 복잡도는 매우 넉넉한 편이다.
이러한 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도 분류되며, 구현이 중요한 대표적인 문제 유형이다. 다만, 알고리즘 교재나 문제 풀이 사이트에 따라서 다르게 일컬을 수 있으니, 코딩 테스트에서의 시뮬레이션, 구현, 완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억하자.

상하좌우 문제를 풀려면, 2차원 공간상에서 좌표의 이동을 코드로 어떻게 표현하는지 알아야 한다.

위 그림과 같이 행은 x축 방향, 열은 y축 방향이라 여기고, 두 개의 배열을 이용하여 2차원 공간상에서 좌표의 이동을 표현할 수 있다. 즉, 동쪽은 y축 방향으로 +1, 서쪽은 y축 방향으로 -1, 남쪽은 x축 방향으로 +1, 북쪽은 x축 방향으로 -1만큼 좌표를 이동시키면 된다. 위 그림에서 (2,2)에 있던 점은 반복문에서 동, 북, 서, 남을 거쳐 원래 자리로 돌아오게 된다.

그래서 상하좌우 문제는 파이썬으로 다음과 같이 풀 수 있다.

n = int(input())
x, y = 1, 1
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)):
		if plan == 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, y = nx, ny

print(x, y)

C++로 풀면 다음과 같다.

#include<iostream>
#include<string>
using namespace std;

int x = 1, y = 1; // 초기 위치

// L, R, U, D에 따른 이동 방향
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
char moveTypes[4] = {'L', 'R', 'U', 'D'};

int main() {
	int n;
	cin >> n; // 정사각행렬의 크기

	// cin으로 입력 받으면 엔터가 버퍼에 남아있기 때문에,
	// 다음 입력을 받기 위해서는 반드시 버퍼를 비워줘야 한다.
	cin.ignore(); 

	// 몇개의 문자를 입력할지 모르기 때문에 문자열 한 줄 전체를 입력 받는다.
	string plans;
	getline(cin, plans);

	// 이동 계획을 하나씩 확인
        for (int i = 0; i < plans.size(); i++) {
            char plan = plans[i];

            // 이동 후 좌표 구하기 
            int nx = -1, ny = -1;
            for (int j = 0; j < 4; j++) {
                if (plan == moveTypes[j]) {
                    nx = x + dx[j];
                    ny = y + dy[j];
                }
            }

            // 공간을 벗어나는 경우 무시 
            if (nx < 1 || ny < 1 || nx > n || ny > n) 
                continue;

            // 공간을 벗어나지 않을 때만 이동 수행 
            x = nx;
            y = ny;
        }

    cout << x << ' ' << y << '\n';

    return 0;
}