백준 2873 자바 - 롤러코스터

https://www.acmicpc.net/problem/2873

2873번: 롤러코스터

문제

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int r, c;
    static StringBuilder sb = new StringBuilder();
    static String[][] board;

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");

        r = Integer.parseInt(st1.nextToken());
        c = Integer.parseInt(st1.nextToken());

        board = new String[r][c];

        if (r % 2 != 0) {
            for (int i = 0; i < r / 2; i++) rightDownLeftDown(c);
            for (int i = 0; i < c - 1; i++) sb.append('R');
            System.out.println(sb);
            return;
        }
        if (c % 2 != 0) {
            for (int i = 0; i < c / 2; i++) downRightUpRight(r);
            for (int i = 0; i < r - 1; i++) sb.append('D');
            System.out.println(sb);
            return;
        }

        int tr = 0, tc = 0;
        int min = 1000;
        for(int i = 0; i < r; i++) {
            board[i] = br.readLine().split(" ");
            for (int j = 0; j < c; j++) {
                int cur = Integer.parseInt(board[i][j]);
                if ((i + j) % 2 == 0 || min <= cur) continue;
                min = cur;
                tr = i + 1;
                tc = j + 1;
            }
        }

        for (int i = 0; i < (tr - 1) / 2; i++) rightDownLeftDown(c);
        for (int i = 0; i < (tc - 1) / 2; i++) sb.append('D').append('R').append('U').append('R');

        if (tr % 2 == 1) sb.append('D').append('R');
        else sb.append('R').append('D');

        int len = (c - tc) / 2;

        if (len != 0) sb.append('R');

        for (int i = 0; i < len; i++) {
            sb.append('U').append('R').append('D');
            if (i != len-1)  sb.append('R');
        }

        len = (r - tr) / 2;

        if (len != 0) sb.append('D');

        for (int i = 0; i < len; i++) {
            leftDownRight(c);
            if (i != len-1) sb.append('D');
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        br.close();
        bw.close();
    }

    static void rightDownLeftDown(int c) {
        for (int i = 0; i < c - 1; i++) sb.append('R');
        sb.append('D');
        for (int i = 0; i < c - 1; i++) sb.append('L');
        sb.append('D');
    }

    static void downRightUpRight(int r) {
        for (int i = 0; i < r - 1; i++) sb.append('D');
        sb.append('R');
        for (int i = 0; i < r - 1; i++) sb.append('U');
        sb.append('R');
    }

    static void leftDownRight(int c) {
        for (int i = 0; i < c - 1; i++) sb.append('L');
        sb.append('D');
        for (int i = 0; i < c - 1; i++) sb.append('R');
    }

}

풀이

코드가 어딘가 어수선 하다. r, c가 모두 짝수가 들어온 경우, 한 칸만 못 지나가면서, 지그재그를 그리며 지나가야 하는 구간이 있는데, 여기를 찾아내는 것과 동시에 움직이는 경로를  알아내야 하기 때문에 골치 아프다.