2873

롤러코스터  : https://www.acmicpc.net/problem/2873

 

참조 사이트 :  https://dundung.tistory.com/45

 

확인용 input

4 3
5 1 3
2 4 8
1 1 2 
1 1 1

3 4
5 1 3 1
2 4 8 1
1 1 2 1

4 4
10 10 10 10
1  10 10 10
10 10 10 10
10 10 10 10

 

참조 사이트에서 흰색칸을 피해가는 경우, 그 칸을 포함 총 3개를 놓치게 된다. 

따라서 4by 4의 경우 아래와 같이 나왔다.

S 1 3 1

1 3 1 3

3 1 3 1

1 3 1 E

 

어떻게 풀까 고민을 했지만 떠오르는 것이 없었다.

 

사이트를 확인해보니, 흑/백 체스판을 구별을 하고, 3인 부분은 무시하고 1로 구성된 부분에서 최소값을 찾아 그 부분만 지나지 않도록 구현을 하더라 (이 부분에서 탐욕법이 적용되었다고 생각한다.)

 

X 10 X 10

10 X 10 X

X 10 X 10

1 X 10 X

 

이런 식으로 두고 최소값을 찾아 주는데, 루프에서 (i+j)%2==0인 부분만 확인하면된다.

나머지 풀이법은 사이트 참조.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {

	static int R, C;
	static boolean DBG = false;
	static int[][] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		arr = new int[R][C];

		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		StringBuilder sb = new StringBuilder();
		StringBuilder sb2 = new StringBuilder();

		if (R % 2 == 1) {
			for (int i = 0; i < R; i++) {
				if (i % 2 == 0) {
					for (int j = 0; j < C-1; j++) {
						sb.append('R');
					}
					if ( i != R-1)
						sb.append('D');						
				} else {
					for (int j = C - 2; j >= 0; j--) {						
						sb.append('L');
					}
					sb.append('D');	
				}

			}
		} else if (C % 2 == 1) {
			for (int i = 0; i < C; i++) {
				if (i % 2 == 0) {
					for (int j = 0; j < R-1; j++) {
						sb.append("D");
					}
					if ( i != C-1)
						sb.append("R");
					
				} else {
					for (int j = R - 2; j >= 0; j--) {
						sb.append( "U");
					}
					sb.append("R");
				}
			}

		} else {// 둘다 짝수
			int min = Integer.MAX_VALUE;
			int mc = 0, mr = 0;
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if ((i + j) % 2 == 1) {
						if (arr[i][j] < min) {
							min = arr[i][j];
							mr = i;
							mc = j;
						}
					}
				}
			}
			int sr = 0;
			int sc = 0;
			int er = R - 1;
			int ec = C - 1;

			while (er - sr > 1) {

				if (sr / 2 < mr / 2) {
					int tmp = C - 1;
					while (tmp-- > 0)
						sb.append('R');
					sb.append('D');
					tmp = C - 1;
					while (tmp-- > 0)
						sb.append('L');
					sb.append('D');
					sr += 2;
				}

				if (mr / 2 < er / 2) {
					int tmp = C - 1;
					while (tmp-- > 0)
						sb2.append('R');
					tmp = C - 1;
					
					sb2.append('D');
					while (tmp-- > 0)
						sb2.append('L');
					sb2.append('D');
					er -= 2;
				}
			}

			while (ec - sc > 1) {
				if (sc / 2 < mc / 2) {
					sb.append('D');
					sb.append('R');
					sb.append('U');
					sb.append('R');
					sc += 2;
				}
				if (mc / 2 < ec / 2) {
					sb2.append('D');
					sb2.append('R');
					sb2.append('U');
					sb2.append('R');
					ec -= 2;
				}
			}
			if (sr == mr) {
				sb.append('D');
				sb.append('R');
			} else {
				sb.append('R');
				sb.append('D');
			}
			sb.append(sb2.reverse());
		}
		System.out.println(sb);
	}

}