도토리를 주워라

NYPC 2021 · 예선 연습문제

[바람의나라]에 있는 욕심쟁이 다람쥐는 도토리를 주으러 위험을 무릅쓰고 $N \times N$ 크기의 초보자사냥터에 왔다. 사냥터에는 여기저기 도토리들이 널려 있는데, 도토리가 있는 곳으로 이동하면 도토리를 주울 수 있다. 사냥터에는 게임을 하고 있는 유저들이 "넥슨은 다람쥐를 뿌려라!"를 외치며 다람쥐가 나타나기를 기다리고 있다. 유저들은 자리를 이동하지는 않지만 욕심쟁이 다람쥐가 유저가 있는 곳으로 가면 유저에게 공격을 받기 때문에 유저가 있는 칸으로 갈 수 없다. 욕심쟁이 다람쥐는 몸이 무겁기 때문에 위로 올라가지 못하고, 왼쪽, 오른쪽, 아래로만 움직일 수 있다.

욕심쟁이 다람쥐가 최대한 많은 도토리를 챙겨 사냥터를 빠져나갈 수 있게 하자.

욕심쟁이 다람쥐의 시작 위치는 맨 왼쪽 위 칸으로 고정되어 있다. 그리고 사냥터의 출구는 맨 오른쪽 아래 칸에 있다. 출구에 도달했을 때, 바로 사냥터를 빠져나가지 않고 다른 곳을 다녀왔다가 다시 출구로 돌아올 수 있다. 아래로 한 칸 이동하는 것을 D, 왼쪽으로 한 칸 이동하는 것을 L, 오른쪽으로 한 칸 이동하는 것을 R로 표현했을 때, <그림 1>의 상황에서 RRRLDDLLRRRRDDLLRR로 이동하면 총 8개의 도토리를 주우며 출구에 도달할 수 있고, 이보다 더 많은 도토리를 주우면서 출구에 도달할 수 없다.

입력 형식

첫째 줄에 사냥터의 크기 $N$ 이 주어진다. ( $5 \le N \le 50$ )

그 다음 $N$ 개의 줄에 사냥터의 상황이 주어진다. 각 줄은 길이가 $N$ 인 문자열로 이루어져 있고, 문자 .는 아무 것도 없는 칸을, 문자 D는 도토리가 놓여져 있는 칸을, 문자 U는 유저가 있는 칸을 의미한다.

욕심쟁이 다람쥐가 시작하는 칸과 출구가 있는 칸은 항상 비어있으며, 욕심쟁이 다람쥐가 출구에 도달할 수 없는 입력은 주어지지 않는다.

출력 형식

욕심쟁이 다람쥐가 움직이는 과정을 나타내는 이동 커맨드를 출력한다. 욕심쟁이 다람쥐가 왼쪽으로 한 칸 움직이면 L, 오른쪽으로 한 칸 움직이면 R, 아래로 한 칸 움직이면 D로, 움직인 순서에 따라 하나의 문자열로 만들어 출력한다. 단, 출력하는 이동 커맨드의 길이가 $1\,000\,000$ 을 넘으면 안 된다.

욕심쟁이 다람쥐는 주어지는 입력 상황에서 가장 많은 도토리를 주우며 출구에 도달해야 한다. 출구에 도달한 이후에 마저 움직일 수 있으며, 최종 종료 위치는 반드시 출구여야 한다. 움직이는 도중에 유저가 있는 칸으로 들어가거나 사냥터 밖으로 나가거나 하면 안 된다. 만약, 가능한 답이 여러 가지인 경우 그중 아무거나 하나 출력한다.