문제 개요
2차원 평면에 두 점 a와 b가 있으며, 각각 좌표 (x1, y1)과 (x2, y2)를 가지고 있다고 가정해 보겠습니다. 현재 우리는 점 a에 위치해 있으며, 한 번에 수직 또는 수평 방향으로 거리 1만큼만 이동할 수 있습니다.
목표는 점 a에서 점 b로 이동한 뒤 다시 점 a로 돌아오고, 이후 또다시 점 b로 이동하는 전체 여정의 이동 과정을 찾아 출력하는 것입니다. 단, 점 a와 b를 제외한 어떤 점도 두 번 이상 지나갈 수 없습니다.
이동 방향은 다음과 같이 문자로 표현합니다.
- R : 오른쪽으로 이동
- L : 왼쪽으로 이동
- U : 위로 이동
- D : 아래로 이동
또한 이 문제에서는 항상 x2 > x1이고 y2 > y1이라는 조건이 성립한다는 점에 유의해야 합니다.
예를 들어 입력이 x1 = 0, y1 = 1, x2 = 3, y2 = 4라면 출력은 다음과 같습니다.
UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU
해결 접근 방법
이 문제는 미리 정해진 이동 패턴에 따라 결과 문자열을 차례대로 구성하면 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 세로 방향 차이(y2 − y1)만큼 위로(U) 이동한 뒤, 가로 방향 차이(x2 − x1)만큼 오른쪽(R)으로 이동하여 점 b에 도착합니다.
- 이어서 아래(D)와 왼쪽(L)으로 이동하여 점 a로 복귀합니다.
- a와 b 외의 점을 중복 방문하지 않도록, 직선 경로 대신 "LU", "RD" 같은 우회 이동을 활용해 경로를 살짝 비껴가도록 만듭니다.
- 마지막으로 우회 패턴을 포함하여 다시 점 b까지 이동하는 경로를 완성합니다.
위 과정을 의사 코드로 나타내면 다음과 같습니다.
s := 빈 문자열 i := 0으로 초기화, i < y2 - y1인 동안(i를 1씩 증가): s의 끝에 "U" 추가 i := 0으로 초기화, i < x2 - x1인 동안(i를 1씩 증가): s의 끝에 "R" 추가 i := 0으로 초기화, i < y2 - y1인 동안(i를 1씩 증가): s의 끝에 "D" 추가 i := 0으로 초기화, i < x2 - x1인 동안(i를 1씩 증가): s의 끝에 "L" 추가 s의 끝에 "LU" 추가 i := 0으로 초기화, i < y2 - y1인 동안(i를 1씩 증가): s의 끝에 "U" 추가 i := 0으로 초기화, i < x2 - x1인 동안(i를 1씩 증가): s의 끝에 "R" 추가 s의 끝에 "RD" 추가 s의 끝에 "RD" 추가 i := 0으로 초기화, i < y2 - y1인 동안(i를 1씩 증가): s의 끝에 "D" 추가 i := 0으로 초기화, i < x2 - x1인 동안(i를 1씩 증가): s의 끝에 "L" 추가 s의 끝에 "LU" 추가 return s
예제: C++ 구현
보다 나은 이해를 위해 다음 C++ 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
string solve(int x1, int y1, int x2, int y2){
string s = "";
for(int i = 0; i < y2 - y1; i++)
s.append("U");
for(int i = 0; i < x2 - x1; i++)
s.append("R");
for(int i = 0; i < y2 - y1; i++)
s.append("D");
for(int i = 0; i < x2 - x1; i++)
s.append("L");
s.append("LU");
for(int i = 0; i < y2 - y1; i++)
s.append("U");
for(int i = 0; i < x2 - x1; i++)
s.append("R");
s.append("RD");
s.append("RD");
for(int i = 0; i < y2 - y1; i++)
s.append("D");
for(int i = 0; i < x2 - x1; i++)
s.append("L");
s.append("LU");
return s;
}
int main() {
int x1 = 0, y1 = 1, x2 = 3, y2 = 4;
cout << solve(x1, y1, x2, y2);
return 0;
}
입력
0, 1, 3, 4
출력
UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU