BOJ_2873_롤러코스터 (Java)

[Platinum III] 롤러코스터 - 2873

문제 링크

성능 요약

메모리: 73500 KB, 시간: 696 ms

분류

해 구성하기, 그리디 알고리즘, 구현

제출 일자

2025년 1월 6일 20:36:02

문제 설명

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

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

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

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

입력

첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.

출력

첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.

문제 풀이

처음엔 짝수x짝수부분을 dfs로 풀었는데 시간초과가 났다. 이에 내가 생각하는 최적의 패턴이 존재했기에 이대로 출력해야겠다고 생각했고, 효율적인 계산을 위해 2묶음(행단위)으로 나눠 처리해줬다.

2차원배열을 마음대로 다루는 연습이 되었다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int R, C, board[][], res;
	static int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};
	static String[] dir = {"R", "D", "L", "U"};
	static boolean[][] visited;
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		board = new int[R][C];
		visited = new boolean[R][C];
		for(int i=0; i<R; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<C; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		boolean flag = false; // 모두 순회해도 되면 true, 안되면(짝수 x 짝수) false
		
		flag = !(R%2==0 && C%2==0);
		if(flag) findAll();
		else findExceptMin();

		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	private void findExceptMin() {
		int min = Integer.MAX_VALUE;
		int minR = -1, minC = -1;
		
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				if((i+j)%2 == 1 && board[i][j] < min) {
					min = board[i][j];
					minR = i;
					minC = j;
				}
			}
		}
		
		for(int i=0; i<minR/2; i++) {
	        // 첫 행은 오른쪽으로
	        for(int j=0; j<C-1; j++) {
	            sb.append("R");
	        }
	        sb.append("D");
	        // 두번째 행은 왼쪽으로
	        for(int j=0; j<C-1; j++) {
	            sb.append("L");
	        }
	        sb.append("D");
	    }
		
		int c = 0;
		int r = 2 * (minR/2); // 최솟값 존재 묶음 중 윗줄 
		int nextR = r+1; // 최솟값 존재 묶음 중 아랫줄
		
		while(r != nextR || c != C-1) {
			if(r < nextR && (c != minC || nextR != minR)) {
				r++;
				sb.append("D");
			}
			else if(r == nextR && (c != minC || nextR-1 != minR)) {
				r--;
				sb.append("U");
			}
			
			if(c != C-1) {
	            c++;
	            sb.append("R");
	        }
		}
		
		// 남은 묶음들
	    for(int i=minR/2+1; i<R/2; i++) {
	        sb.append("D");
	        for(int j=0; j<C-1; j++) {
	            sb.append("L");
	        }
	        sb.append("D");
	        for(int j=0; j<C-1; j++) {
	            sb.append("R");
	        }
	    }
		
//		visited[minR][minC] = true;
//		dfs(0, 0, 1);
	}

//	private boolean dfs(int r, int c, int cnt) { // 시간초과
//		if(r == R-1 && c == C-1) return cnt == R * C - 1;
//		
//		visited[r][c] = true;
//		
//		for(int k=0; k<4; k++) {
//			int nr = r + dr[k];
//			int nc = c + dc[k];
//			
//			if(nr >= 0 && nr < R && nc >= 0 && nc < C && !visited[nr][nc]) {
//				sb.append(dir[k]);
//				if(dfs(nr, nc, cnt + 1)) return true;
//				sb.setLength(sb.length()-1);
//			}
//		}
//		
//		visited[r][c] = false;
//		return false;
//	}

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